攻克让你畏惧的算法，十行代码搞定快速排序
The following article is from Coder梁 Author 梁唐
一个热爱分享的推荐算法工程师
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
我们今天接着来看《算法第四版》这本书，在上一篇文章当中我们一起搞定了归并排序。归并排序非常出色，也是性能最好的排序算法之一，这一篇我们继续研究排序问题，来看一看另外一种常用的排序算法——快速排序。
顾名思义，快速排序的特点当然就是快。但其实如果单纯从复杂度的量级来看，快速排序并没有比归并排序更好，它们是同一个量级的算法，只不过它的常数通常会更小。毕竟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++版本，因为它性能更好，也是更常规更标准的实现方式。
这一篇关于快速排序的实现就先聊到这里，之后我们会再来聊聊快排的优化，以及复杂度的问题。
程序员专属卫衣
商品直购链接 👇
推荐阅读：
每日打卡赢积分兑换书籍入口