快速排序核心原理与多版本实现详解

关键点说明：为什么 left 和 right 指定的数据和 key 值相等时不能直接交换？这涉及到指针移动的逻辑边界，若处理不当可能导致死循环或基准值错位。

性能分析

在最优情况下，每次划分都能将数组均匀分成两部分，递归树会有 logN 层，每层处理约 N 个元素，总时间复杂度为 O(NlogN)。需要注意的是，如果数组本身有序，无法达到均分，此时会退化为 O(n²)。实际应用中我们会通过优化让快排尽可能接近平衡二叉树的状态。

有序情况优化

随机选 keyi

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

int randi = left + rand() % (right - left + 1);
swap(&a[randi], &a[keyi]);

三数取中

通过 GetMidNumi 函数从区间的左、中、右三个位置选出数值居中的元素下标，将其交换到区间左端点作为基准值，以此避免在有序数组中选到极值导致的性能退化。

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 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;
    
    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;
    }
}

// 在 QuickSort3 中加入判断
if ((right - left + 1) < 15) {
    InsertSort(a + left, right - left + 1);
    return;
}

小区间优化的阈值一般设置为 10~20（行业通用经验值，最常用的是 15）。

迭代版本（非递归）

递归版快排虽逻辑清晰，但存在函数调用开销与递归深度过大导致的栈溢出风险。可通过手动维护栈来模拟递归调用，实现非递归版本。

非递归思路：用栈模拟递归调用，先压入整个数组的边界，然后循环弹出边界、分区，再把左右子区间的边界压入栈，直到栈为空，排序完成。

代码实现

void QuickSortNonR(int* a, int left, int right) {
    Stack st;
    STInit(&st);
    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;
        }
        
        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;
    
    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--;
        } else if (a[cur] < key) {
            swap(&a[begin], &a[cur]);
            begin++;
            cur++;
        } else {
            cur++;
        }
    }
    
    QuickSortT(a, left, begin - 1);
    QuickSortT(a, end + 1, right);
}

效率对比