快速排序核心原理与多种实现优化详解

常见问题：为什么 left 和 right 指定的数据和 key 值相等时不能交换？这会导致死循环或逻辑错误，具体可参考指针移动轨迹图。

时间复杂度分析

在最优情况下，每次划分都能将数组均匀分成两部分。递归树有 logN 层，每层处理约 N 个元素，总时间复杂度为 O(NlogN)。

如果数组本身有序，还能达到均分吗？显然不能，此时会退化为 O(n²)。

实际应用中，我们会通过优化让快排尽可能接近平衡二叉树的状态。

有序情况优化

随机选 Key

即使输入是有序数组，随机选择基准也能大概率避免每次都选到最左/最右元素，将最坏时间复杂度 O(n²) 优化为概率上的 O(nlogN)。

void QuickSort1(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int begin = left;
    int end = right;
    int keyi = left;
    
    // 优化 1：随机选 keyi
    int randi = left + rand() % (right - left + 1);
    swap(&a[randi], &a[keyi]);
    
    while (begin < end) {
        while (begin < end && a[end] >= a[keyi]) {
            end--;
        }
        while (begin < end && a[begin] <= a[keyi]) {
            begin++;
        }
        swap(&a[begin], &a[end]);
    }
    
    swap(&a[keyi], &a[begin]);
    keyi = begin;
    
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

三数取中

通过比较左、中、右三个位置的元素，选出居中的值作为基准，进一步避免极端情况。

int GetMidNumi(int* a, int left, int right) {
    int midi = (right + left) / 2;
    if (a[left] < a[midi]) {
        if (a[right] < a[left]) {
            return left;
        } else if (a[right] > a[midi]) {
            return midi;
        } else {
            return right;
        }
    } else {
        if (a[right] > a[left]) {
            return left;
        } else if (a[midi] > a[right]) {
            return midi;
        } else {
            return right;
        }
    }
}

void QuickSort1(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int begin = left;
    int end = right;
    int keyi = left;
    
    // 优化 2：三数取中
    int midi = GetMidNumi(a, left, right);
    swap(&a[midi], &a[keyi]);
    
    while (begin < end) {
        while (begin < end && a[end] >= a[keyi]) {
            end--;
        }
        while (begin < end && a[begin] <= a[keyi]) {
            begin++;
        }
        swap(&a[begin], &a[end]);
    }
    
    swap(&a[keyi], &a[begin]);
    keyi = begin;
    
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

提示：随机选基准和三数取中二选一即可，主要目的是避免有序数组下的性能退化。但面对大量重复数据时效率仍会下降，后续将介绍三路划分。

稳定性分析

由于分区过程中存在跨位置交换，相等元素的相对顺序可能被破坏，因此快速排序是不稳定的排序算法。

三、挖坑法

挖坑法介绍

以升序为例，先选一个基准值并把它的位置设为第一个'坑'。右指针从后向前找比基准值小的元素填入左坑，左指针再从前向后找比基准值大的元素填入右坑，不断形成新坑，直到双指针相遇，最后把基准值填入最终的坑位。

如果是降序，只需调整查找条件：右指针找大，左指针找小。

代码实现

void QuickSort2(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int key = a[left];
    int hole = left;
    int begin = left;
    int end = right;
    
    // 随机选 keyi 优化
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[hole]);
    
    while (begin < end) {
        // 右边先走，找小
        while (begin < end && key <= a[end]) {
            end--;
        }
        a[hole] = a[end];
        hole = end;
        
        // 左边后走，找大
        while (begin < end && key >= a[begin]) {
            begin++;
        }
        a[hole] = a[begin];
        hole = begin;
    }
    
    // 让基准值入坑
    a[hole] = key;
    
    QuickSort2(a, left, hole - 1);
    QuickSort2(a, hole + 1, right);
}

四、Lomuto 前后指针版本

Lomuto 版本介绍

核心思路：选一个基准值，prev 和 cur 初始指向同一位置。cur 从左向右遍历，遇到比基准值小的元素时，prev 右移一位并交换二者；遇到大的则 cur 直接右移。遍历结束后，交换 prev 与基准值位置。

代码实现

void QuickSort3(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    
    // 随机选 keyi 优化
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[keyi]);
    
    while (cur <= right) {
        if (a[cur] < a[keyi]) {
            prev++;
            swap(&a[prev], &a[cur]);
            cur++;
        } else {
            cur++;
        }
    }
    
    swap(&a[prev], &a[keyi]);
    keyi = prev;
    
    QuickSort3(a, left, keyi - 1);
    QuickSort3(a, keyi + 1, right);
}

小区间优化

当递归到小区间时，继续使用快速排序的开销可能超过收益。此时采用插入排序等简单算法，能减少递归深度和调用次数。

void InsertSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = a[i + 1];
        while (end >= 0) {
            if (a[end] > tmp) {
                a[end + 1] = a[end];
                end--;
            } else {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

void QuickSort3(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    // 小区间优化
    if ((right - left + 1) < 15) {
        InsertSort(a + left, right - left + 1);
        return;
    }
    
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[keyi]);
    
    while (cur <= right) {
        if (a[cur] < a[keyi]) {
            prev++;
            swap(&a[prev], &a[cur]);
            cur++;
        } else {
            cur++;
        }
    }
    
    swap(&a[prev], &a[keyi]);
    keyi = prev;
    
    QuickSort3(a, left, keyi - 1);
    QuickSort3(a, keyi + 1, right);
}

小区间阈值通常设置为 10~20，行业通用经验值是 15。

五、迭代版本（非递归）

递归的缺陷

递归版快排逻辑清晰，但存在函数调用开销与栈溢出风险。可通过手动维护栈来模拟递归调用。

非递归思路

用栈模拟递归：压入整个数组边界，循环弹出边界进行分区，再将左右子区间边界压入栈，直到栈空。

代码实现

void QuickSortNonR(int* a, int left, int right) {
    Stack st;
    STInit(&st);
    
    // 入 [left, right] 区间
    STPush(&st, right);
    STPush(&st, left);
    
    while (!STEmpty(&st)) {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
        
        // 小区间优化
        if (end - begin + 1 < 15) {
            InsertSort(a + begin, end - begin + 1);
            continue;
        }
        
        // 随机选 keyi
        int randi = begin + (rand() % (end - begin + 1));
        swap(&a[randi], &a[begin]);
        
        // 前后指针版本
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        
        while (cur <= end) {
            if (a[cur] < a[keyi]) {
                prev++;
                swap(&a[cur], &a[prev]);
                cur++;
            } else {
                cur++;
            }
        }
        
        swap(&a[prev], &a[keyi]);
        keyi = prev;
        
        // 子区间处理
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
    }
    
    STDestroy(&st);
}

六、三路划分

三路划分思想

将数组一次分成小于基准、等于基准、大于基准三部分。等于基准的元素已就位不再递归，只递归左右两区。这对大量重复数据效率极高。

代码实现

void QuickSortT(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    // 小区间优化
    if ((right - left + 1) < 15) {
        InsertSort(a + left, right - left + 1);
        return;
    }
    
    int begin = left;
    int end = right;
    int cur = left + 1;
    
    // 随机选 keyi
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[left]);
    int key = a[left];
    
    while (cur <= end) {
        if (a[cur] > key) {
            swap(&a[cur], &a[end]);
            end--;
            // 不能直接 ++cur，因为从尾部交换过来的值还没检查过
        } else if (a[cur] < key) {
            swap(&a[begin], &a[cur]);
            begin++;
            cur++; // begin 的值已被检查过，可直接 ++
        } else {
            cur++;
        }
    }
    
    QuickSortT(a, left, begin - 1);
    QuickSortT(a, end + 1, right);
}

效率对比