快速排序核心原理與 C 語言遞歸實現詳解

算法定位

快速排序是冒泡排序的本質改進，採用分治策略：一趟掃描將序列分為左右兩部分，左邊全 ≤ 樞軸，右邊全 ≥ 樞軸，遞歸處理子序列。

核心概念：樞軸

選取一個關鍵字作為基準，經過分區操作將其放至最終位置，左側元素均不大於它，右側均不小於它。常用策略：取最左端元素。

分區算法

int Partition(int arr[], int low, int high) {
    int pivotkey = arr[low];  // 樞軸值
    while (low < high) {
        while (low < high && arr[high] >= pivotkey) high--;
        swap(arr, low, high);  // 小元素移到低端
        while (low < high && arr[low] <= pivotkey) low++;
        swap(arr, low, high);  // 大元素移到高端
    }
    return low;  // 樞軸最終位置
}

遞歸主流程

void QuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot-1);   // 左子序列
        QuickSort(arr, pivot+1, high);  // 右子序列
    }
}

完整可運行示例

#include <stdio.h> #include <stdlib.h>
void swap(int arr[], int i, int j) { int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
int Partition(int arr[], int low, int high) { ... }
void QuickSort(int arr[], int low, int high) { ... }
void print(int arr[], int n) { for(int i=0;i

複雜度全景分析

情況
分區特徵
遞歸深度
時間複雜度
最優
每次均勻二分
log₂n
O(n log n)
最壞
正序/逆序，單邊為空
n-1
O(n²)
平均
隨機分佈
~1.39 log₂n
O(n log n)


關鍵特性

不穩定排序：相等元素相對位置可能改變
原地排序：輔助空間 O(log n) 遞歸棧
緩存友好：順序訪問，實際表現優於同級算法


工程優化方向

小區間改用插入排序（閾值 10~20）
三數取中法選樞軸，避免最壞情況
尾遞歸優化 / 手動棧模擬非遞歸版
雙向掃描 / 三向切分（處理大量重複鍵）


快速排序是基於比較的內部排序中平均性能最優的算法，工程廣泛採用（如 std::qsort、Java Arrays.sort 基礎版）。