快速排序算法原理与多种实现方式详解

**问题 1：**为什么 left 和 right 指定的数据和 key 值相等时不能交换？

3、时间复杂度分析

这张图展示的是快速排序在最优情况下的时间复杂度推导：每次划分都能将数组均匀分成两部分，递归树会有 logN 层，且每一层都需要处理约 N 个元素，总的时间复杂度为 O(NlogN)。

有些同学可能会疑惑，为啥每层遍历的元素都是 N？实际上每层遍历的元素个数是 N 减去该层基准值的数量，但基准值数量相对于 N 是低阶项，在大 O 表示法中可以忽略不计，因此我们仍认为每层总遍历元素数约为 N。

那如果数组是有序的情况还能达到均分吗？显而易见，不能。

但是在实际中我们会对快排进行优化，让其能近似达到一个平衡二叉树的状态。

4、有序情况优化

4.1 随机选 keyi

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]);
    // 处理 [begin end] 区间
    // 当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置
    while (begin < end) {
        // 右边找小：升序
        while (begin < end && a[end] >= a[keyi]) {
            end--;
        }
        // 左边找大：升序
        while (begin < end && a[begin] <= a[keyi]) {
            begin++;
        }
        // 找到后交换
        swap(&a[begin], &a[end]);
    }
    // 走到这代表 begin 和 end 当前位置就是 key 的合适位置
    swap(&a[keyi], &a[begin]);
    keyi = begin;
    // 递归子区间
    // [left keyi - 1] keyi [keyi + 1 right]
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

即使输入是有序数组，随机选基准也能大概率避免'每次选到最左 / 最右元素'，让递归树尽可能平衡，将最坏时间复杂度 O(n²) 优化为概率上的 O(nlogn)。

4.2 三数取中

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 // a[left] > a[midi]
    {
        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]);
    // 处理 [begin end] 区间
    // 当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置
    while (begin < end) {
        // 右边找小：升序
        while (begin < end && a[end] >= a[keyi]) {
            end--;
        }
        // 左边找大：升序
        while (begin < end && a[begin] <= a[keyi]) {
            begin++;
        }
        // 找到后交换
        swap(&a[begin], &a[end]);
    }
    // 走到这代表 begin 和 end 当前位置就是 key 的合适位置
    swap(&a[keyi], &a[begin]);
    keyi = begin;
    // 递归子区间
    // [left keyi - 1] keyi [keyi + 1 right]
    QuickSort1(a, left, keyi - 1);
    QuickSort1(a, keyi + 1, right);
}

这段代码为快速排序实现了三数取中优化，核心是通过 GetMidNumi 函数从区间的左、中、右三个位置中选出数值居中的元素下标，将其交换到区间左端点作为基准值，以此避免在有序数组中选到极值导致的性能退化，让递归树更接近平衡，从而将时间复杂度稳定在 O(NlogN)。

提示：随机选基准和三数取中可避免快排在有序数组下的性能退化，二选一即可；但面对大量重复数据时效率仍会下降，后续将介绍三路划分来解决这一问题。

5、稳定性分析

由于快排在分区过程中会进行跨位置的交换操作（例如 swap(&a[cur], &a[prev])），这会打乱相等元素的相对位置，因此快速排序是不稳定的排序算法。

三、挖坑法

1、挖坑法介绍

挖坑法快排（以升序为例）的核心思路是：先选一个基准值并把它的位置设为第一个'坑'，然后用右指针从后向前找比基准值小的元素填入左坑，左指针再从前向后找比基准值大的元素填入右坑，不断形成新坑，直到双指针相遇，最后把基准值填入最终的坑位完成分区，再递归排序左右子区间。

如果是降序排序，只需调整指针查找条件：右指针找比基准值大的元素，左指针找比基准值小的元素即可。

2、编码实操

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]);
    // 相等就表示已经为 Key 找到合适的坑位了
    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;
    // [left hole - 1] hole [hole + 1 right]
    // 递归子区间
    QuickSort2(a, left, hole - 1);
    QuickSort2(a, hole + 1, right);
}

四、Lomuto 前后指针版本

1、前后指针版本介绍

Lomuto 前后指针版快排（以升序为例）的核心思路是：先选一个基准值，初始时 prev 和 cur 指向同一位置，然后用 cur 指针从左向右遍历，遇到比基准值小的元素时，prev 右移一位并交换二者位置；遇到比基准值大的元素时，cur 直接右移。遍历结束后，交换 prev 与基准值的位置完成分区，再递归排序左右子区间。

如果是降序排序，只需调整指针查找条件：cur 指针找比基准值大的元素即可。

2、编码实操

void QuickSort3(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    int keyi = left;
    // prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置
    int prev = left;
    int cur = left + 1;
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[keyi]);
    while (cur <= right) {
        // cur 找到了小于 key 的值
        if (a[cur] < a[keyi]) {
            prev++;
            swap(&a[prev], &a[cur]);
            cur++;
        } else {
            cur++;
        }
    }
    swap(&a[prev], &a[keyi]);
    keyi = prev;
    // [left keyi - 1] keyi [keyi + 1 right]
    QuickSort3(a, left, keyi - 1);
    QuickSort3(a, keyi + 1, right);
}

3、小区间优化

在快速排序中，小区间优化是一种常见的优化策略。当递归到小区间时，继续使用快速排序可能会因为递归调用的开销而导致性能下降。此时采用插入排序等简单排序算法来处理小区间，能减少递归深度和调用次数，降低栈空间的使用，同时利用插入排序在小规模数据上的优势，从而提高快速排序的综合性能。

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;
    // prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置
    int prev = left;
    int cur = left + 1;
    int randi = left + (rand() % (right - left + 1));
    swap(&a[randi], &a[keyi]);
    while (cur <= right) {
        // cur 找到了小于 key 的值
        if (a[cur] < a[keyi]) {
            prev++;
            swap(&a[prev], &a[cur]);
            cur++;
        } else {
            cur++;
        }
    }
    swap(&a[prev], &a[keyi]);
    keyi = prev;
    // [left keyi - 1] keyi [keyi + 1 right]
    QuickSort3(a, left, keyi - 1);
    QuickSort3(a, keyi + 1, right);
}

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

五、迭代版本（非递归）

1、递归的缺陷

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

2、非递归思路

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

3、编码实操

void QuickSortNonR(int* a, int left, int right) {
    stack st;
    STInit(&st);
    // 入 [left right] 区间
    // 先入 right 是为了能正确取到 [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;
        // 子区间处理
        // [begin keyi - 1] keyi [keyi + 1 end]
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
    }
    STDestroy(&st);
}

六、三路划分

1、三路划分思想

三路划分思想：把数组一次分成小于基准、等于基准、大于基准三部分，等于基准的元素直接就位不再递归，只递归左右两区，大量重复数据时效率极高，可直接替代普通快排。

2、编码实操

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 的值已经被我们检查过了
            cur++;
        } else {
            cur++;
        }
    }
    // [left begin - 1] [begin end] [end + 1 right]
    QuickSortT(a, left, begin - 1);
    QuickSortT(a, end + 1, right);
}

3、普通快排和三路划分效率对比