vlambda博客
学习文章列表

大家好，我是梁唐。

我们今天接着来看《算法第四版》这本书，在上一篇文章当中我们一起搞定了归并排序。归并排序非常出色，也是性能最好的排序算法之一，这一篇我们继续研究排序问题，来看一看另外一种常用的排序算法——快速排序。

顾名思义，快速排序的特点当然就是快。但其实如果单纯从复杂度的量级来看，快速排序并没有比归并排序更好，它们是同一个量级的算法，只不过它的常数通常会更小。毕竟N和10N、100N说起来都是一样的复杂度，但它们的运行时间却差了上百倍，所以即使是常数的差异也是可以很惊人的。

你可能在《算法导论》的课程或者是某本算法书上看过快排的原理，但也只是看过，可能没过两三天就忘在脑后了。

如果不幸被我言中也不用懊恼，学算法本就是一个曲折的过程。在今天的文章当中，我会试着帮你找到几个关键点，加深对它的印象，从而让你离亲自动手实现它更进一步。

分治和切分

快速排序和归并排序是一对好基友，虽然快速排序的名字里面没有归并或者是分治这两个字，但仍然不妨碍它拥有和归并排序一样的核心原理——分治法。

是的，你没有看过，快速排序也是基于分治的思想实现的。表面上看，分治好像只是做了一点无聊的操作，将一个数组拆分成了两个。但神奇的是，只要这个操作持续进行，就可以化整为零实现我们想要的目标。

在归并排序当中，这个操作是两个有序数组的归并，那么在快速排序当中，又是什么呢？

其实也很简单，这个操作叫做切分。

所谓切分也就是将数组根据指标K拆分成两个部分，其中小于等于K的一个部分，大于K的另外一个部分。比如我们有这么一个数组：

[10, 3, 9, 6, 5, 4, 2, 7]

我们选择的K是5，切分之后，我们把K放在中间，可以写成这样：

[3, 4, 2] 5 [10, 9, 6, 7]

显然，拆分之后的数组依然不是有序的。但我们可以肯定两点，第一：K的位置一定正确了，因为左边都是小于等于它的，右边都是大于它的，所以K切分之后摆放在了正确的位置。第二：切分之后得到的结果比之前更接近排序之后的结果。

从数学角度上来说，它的熵减小了，翻译成人话就是它的有序程度增加了，杂乱程度减小了。毕竟我们摆放好了K，而且让元素按照大小分成了两个部分。

我们来试着写一下切分的过程，我们先用Python来写，再用C++。因为在这个问题上，Python的语法简单很多：

def cut(nums, k):
  le, gt = [], []
  for i in nums:
    if i <= k:
      le.append(i)
    else:
      gt.append(i)
  return le + gt

我们运行测试一下，符合我们的预期。

为什么Python写起来更简单呢，因为Python可以更加方便地拆分和新建List，C++则要麻烦很多。

同样的代码在C++写出来是这样的：

void cut(vector<int>& nums, int K) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        while (nums[l] <= K && l < r) l++;
        while (nums[r] >= K && l < r) r--;
        if (l < r) {
            swap(nums[l], nums[r]);
        }
    }
}

从行数上来看，两者差不多，但C++用到了两指针，总体上更加复杂一些。

切分和排序

理解了切分之后，摆在我们面前的就只剩下了最后一个问题——怎么样用切分来排序呢？

其实我们已经很接近了，只不过少了一个步骤所以看起来还不太明显。我们将数组分成了两个部分，前半部分都小于等于K，后半部分都大于等于K。如果K本身就是数组中的元素，那么它是不是应该放在这两个部分中间？这个中间的位置是不是就是K排序之后应该在的位置？

所以我们一轮切分之后，至少可以确定把K放到应该在的位置。K的位置确定了之后，我们就可以采用分治法，对于K前面和K后面的部分分别如法炮制。只要这样一直操作下去，就一定可以保证数组当中的所有元素都有序。

不要再怀疑，的确如此。

我们来完整地写一下代码，我们先看Python版本的，它绝对比你想的更加简单：

def sort(nums):
    if len(nums) <= 1:
        return nums

    K = nums[-1]
    le, gt = [], []
    for i in range(len(nums)-1):
        if nums[i] <= K:
            le.append(nums[i])
        else:
            gt.append(nums[i])
    return sort(le) + [K] + sort(gt)

在这段代码当中，我们默认选择数组的最后一个元素作为比较的K。其实用字母K表示不太严谨，正规的叫做叫做pivot，翻译过来就是枢纽、转轴的意思。为了便于大家理解，所以没有在一开始的时候介绍过多的概念。

选择了K之后，我们创建两个数组分别存储小于等于K的和大于K的元素。最后，返回的时候把K放在了两者之间。为什么说Python很方便呢，因为Python可以很轻松地对整个数组进行加法操作：

return sort(le) + [K] + sort(gt)

这里一行代码，就把递归和数组拼接全部实现了。

Python的实现方式固然非常方便，但会增加算法的开销。因为创建新的数组、数组销毁，以及数组的合并这些操作都是有开销的。

在C++的版本当中，我们直接在原数组上操作，而非拷贝拼接的方式来执行。除了性能更好之外，也可以避免额外的空间消耗。但代价就是整体的代码会稍微复杂一些。

void quick_sort(vector<int>& nums, int l, int r) {
    if (l >= r) return ;
    int i = l, j = r;
    int K = nums[r];
    while (i < j) {
        while (nums[i] <= K && i < j) i++;
        while (nums[j] >= K && i < j) j--;
        if (i < j) {
            swap(nums[i], nums[j]);
        }
    }
   // 将K放在合适的地方
    swap(nums[r], nums[j]);
    quick_sort(nums, l, j-1);
    quick_sort(nums, j+1, r);
}

void quick_sort(vector<int> &nums) {
    quick_sort(nums, 0, nums.size()-1);
}

其他逻辑和之前的cut一样，注意一下最后一行，它等价于：

nums[r] = nums[j];
nums[j] = K;

由于我们选择了最后一个元素作为K，所以在顺序调整之后，我们要把它放在正确的位置，即右侧指针j最后停留的位置。

如果大家在面试中遇到手写快排的问题，不妨可以选择Python版本。因为它实现更加简单，不容易出错。而在日常的比赛或者是学习当中，建议还是选择C++版本，因为它性能更好，也是更常规更标准的实现方式。

这一篇关于快速排序的实现就先聊到这里，之后我们会再来聊聊快排的优化，以及复杂度的问题。

感谢大家的阅读。