你真的会快速排序吗？

24次阅读

共计 3759 个字符，预计需要花费 10 分钟才能阅读完成。

快速排序(QuickSort)，20世纪十大算法之一，也是公认的平均性能最优的通用排序，由Tony Hoare（C.A.R. Hoare）于1959–1960 年发明，1961–1962 年正式发表。Hoare 也因快速排序、公理语义等贡献，获得了1980 年的图灵奖。快排(快速排序)也在后来成为了C++ std::sort、Java Arrays.sort、Python sorted等标准库的核心。

话不多说，直接看算法的具体思想来体会Hoare大佬的智慧。

QuickSort的核心思想是分治法，分而治之的意思。官方解释就是将一个大问题分成一些规模小的子问题，分别求解子问题之后，再合并子问题得到原先大问题的解。

听起来有点小迷糊。

其实就是一个词：递归，

你看，递不就是将大问题不断分解为小问题，而归就负责将这些小问题都合并起来。

所以分治和递归是一对孪生兄弟。

快排的分的核心思想就是在一堆乱序的数组选一个作为基准值(pivot)，将小于这个pivot的数放在它的左边；小于它的放在它的右边；等于它的数，你可以放在左边，也可以放在右边，或者可以直接放在中间(一般放在左边或中间)。这样一次分区就做完了，接着按照相同的思路，再递归处理左半区小于pivot和右半区大于pivot的部分。也就是一直重复：

从一堆没有排序的数里面找一个数字当基准值，小于这个基准值的数放在它的左边，大于它的放在右边，一样大的放中间(我喜欢放中间)。

没错，就是如此简单，你可能会说：这就能得图灵奖？

我想说的是：我们已经站在了巨人的肩膀上了，所以我们是无法回到那个认定排序就要两层循环，慢是天经地义的年代里再去真切体会这件事的重大。这是一种可惜，也是一种快乐。

下面让我们快乐起来，用代码来实现这个算法。

插播一句，不要听完原理就瞧不起代码，要知道，在 1942 年，二分搜索的思想就被提出，但直到 1962 年第一个没有bug的代码才正式发表。

我们先看快速排序的经典实现，也就是两路快速排序，同时这也是大多数教科书里面的实现方法。

class Solution {
private:
    void swap(vector<int>& nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    int partition(vector<int>& nums, int left, int right, int pivot) {
        int cursor = left;
        int record = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] <= pivot) {
                swap(nums, cursor, i);
                if (nums[cursor] == pivot) {
                    record = cursor;
                }
                cursor++;
            }
        }
        swap(nums, cursor - 1, record);
        return cursor - 1;
    }

    void quicksort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = nums[left + rand() % (right - left + 1)];
        int mid = partition(nums, left, right, pivot);
        quicksort(nums, left, mid - 1);
        quicksort(nums, mid + 1, right);
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) {
            return nums;
        }
        srand((unsigned)time(nullptr));
        quicksort(nums, 0, len - 1);
        return nums;
    }
};

将上方代码放到https://leetcode.cn/problems/sort-an-array/提交，你会发现超出时间限制了，为什么呢？

不急，我们先来看一下代码的实现过程，

首先，swap函数中是交换数组中下标为left和right的两个数的位子；

partition函数里面是两路快速排序的核心逻辑，在left到right范围的数组中，从left开始遍历，只要遍历到的数字小于或者等于基准值的，全部按顺序放到数组的左边去(满足条件的才cursor++)，那这个record = cursor是干嘛的呢？

其实我们按照上面的逻辑进行分区，最后这个数组大于等于cursor的都是大于基准值的，小于cursor的都是小于等于基准值的。

但是，我们并不知道基准值的下标在哪里，cursor – 1位置的数并不一定就是基准值，所以我们直接在分区的时候随便记录一个基准值的下标(代码中记录的是排在左分区最右边的基准值的下标)，接着和下标为(cursor – 1)的数字进行swap，这样(cursor – 1)的位置就是基准值了，最后返回(cursor – 1)。这样，左、右半区分别为[left , cursor – 2 ] 和 [cursor , right]。

然后quicksort函数接着递归处理左半区和右半区就可以了。

quicksort函数中，我们随意从left到right的范围中挑选一个作为pivot(基准值)，这是为什么呢？

我们知道快速排序的平均时间复杂度为 $O$ ( $n$ * $\log n$ ) , 而最坏的时间复杂度为 $O(n^2)$ 。快速排序有一个缺陷，即在有序 / 接近有序数组而导致快排退化为 $O(n^2)$ 时间复杂度。

通过随机选取数组区间 [left, right] 内的一个元素作为基准，打破 “有序数组选固定位置基准（比如最左 / 最右）”导致的最坏情况，让快排的时间复杂度从理论上的最坏 $O(n^2)$ 变成实际运行中几乎不可能出现。

那为什么上面链接中还是会显示超时呢？

这就是两路快排的另外一个缺陷所在了，当数组中存在大量重复元素（比如 [2,2,2,2,2] 或 [1,3,2,3,3,3]）时，算法的时间复杂度还是会退化为 $O(n^2)$ 。

这该如何解决呢？

这就需要用三路快速排序来解决了。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty())
            return nums;

        srand((unsigned)time(NULL));
        int first, last;

        auto swap = [&](int le, int ri) {
            int temp = nums[le];
            nums[le] = nums[ri];
            nums[ri] = temp;
        };

        auto partition = [&](int from, int to, int x) {
            first = from;
            int i = from;
            last = to;
            while (i <= last) {
                if (nums[i] == x) {
                    i++;
                } else if (nums[i] < x) {
                    swap(i++, first++);
                } else {
                    swap(i, last--);
                }
            }
        };

        function<void(int, int)> quickSort;
        quickSort = [&](int l, int r) {
            if (l >= r) {
                return;
            }

            int x = nums[l + rand() % (r - l + 1)];
            partition(l, r, x);

            int left = first;
            int right = last;
            quickSort(l, left - 1);
            quickSort(right + 1, r);
        };

        quickSort(0, nums.size() - 1);
        return nums;
    }
};

为什么三路快排可以解决重复元素过多导致的退化问题？

三路快排的核心改进，是通过三个指针的分区逻辑，把数组明确划分为三个区间，从根本上隔离重复元素 —— 我们直接看它的核心 partition 阶段（以 lambda 表达式实现为例）：

三路快排定义了三个核心 “动点” 指针，将数组 [l, r] 划分为左闭右开的四个区域，即：
1. first：小于区的右边界 → 小于基准值的元素落在 [l, first)；
2. last：大于区的左边界 → 大于基准值的元素落在 (last, r]；
3. i：遍历指针 → 未处理的元素落在 [i, last]；
4. 等于区：[first, i) → 这个区间内全是等于基准值的元素。

遍历指针 i 逐个扫描未处理区间 [i, last]，处理逻辑如下：
1. 若 nums[i] == 基准值：仅将 i++，first 保持不动 → 该元素直接归入「等于区」，无需交换、无需参与后续递归；
2. 若 nums[i] < 基准值：交换 nums[i] 和 nums[first]，然后 i++、first++ → 该元素归入「小于区」，扩展小于区边界；若 nums[i] > 基准值：交换 nums[i] 和 nums[last]，然后 last– → 该元素归入「大于区」，扩展大于区边界（i 不动，因为交换过来的新元素需重新判断）。

所以，三路快排最核心的点就在于—-等于基准值的数会被全部集中放到中间区域，不会被分配到左右区间，也不参与到后续的递归分区中去。

最后的最后，你真的懂快速排序了吗？

不妨自己去试一试吧！

https://leetcode.cn/problems/sort-an-array