知乎盐选会员精选文章终于到了要实现快速排序的时候了。
递归式快速排序
快速排序原理
我们先来回顾一下快速排序的原理，可分为「分」、「治」两步：
分 1.1 分区：将待排数列分成左区、轴和右区； 1.2 对分出来的左区和右区再分别进行分区，持续迭代。
治：当分出来的分区长度为 1 或 0 时，就无须再分了，至此，关于本区域的分区迭代停止。
从原理到实现
如果对应到程序中，2 可以对应为一个判断条件，1.1 是分区函数，那么 1.2 呢？
关于 1.2，我们可以理解为继续进行分区。
比如，将 1.1 分出来的左区，再将左区分为左左区和左右区。如果左左区或左右区不满足长度为 1 或 0 的条件，还要继续对它（们）分区……对右区的操作亦如是。
因此 1.2 并不是简单的重复 1.1，而是援引整个算法本身——这正是递归适合处理的情况。
递归式快排的编程实现
加载中…
所以，我们可以用递归来完成快速排序：
def qSortRecursion(arr, low, high):
if low >= high:
return
p = partition(arr, low, high)
qSortRecursion(arr, low, p – 1)
qSortRecursion(arr, p + 1, high)
return
qSortRecursion()函数接受三个参数：arr，low 和 high：
arr 是自始至终存储所有数字的列表。
low 和 high 是列表中两个单元的下标，分别指向待排序区域的起始坐标。
如此设置，就可以在递归的过程中限制递归的作用域，并使得递归函数待解决的问题越来越小，一直小到待排区域的长度为 1 或者 0（low >= high）为止。
之前我们已经有了分区函数，当时还特地调整了分区函数的参数设置，大家还记得吧？
为什么那样改呢？就是为了和现在这个 qSortRecursion()函数的参数意义保持一致，方便在 qSortRecursion()里调用它。
调用递归快速排序函数：
arr = [7, 9, 6, 8, 10, 3, 2, 1, 4, 5]
qSortRecursion(arr, 0, len(arr) – 1)
print(arr)
输出结果：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
递归式快排 vs 迭代式快排
时间复杂度
无论是递归式快排还是迭代式快排，它们的时间复杂度都是一样。
不过，一边情况下，迭代式快排的运行速度整体上略快于递归式。
究其原因和递归的内部实现有关，其中还牵扯到了我们没有学过的一种数据结构：堆栈，在此就不展开讲了。大家知道这一点即可。
空间复杂度
递归式和迭代式快排的空间复杂度其实都是取决于分区函数——无论那种算法实现，都只有分区函数才需要额外的缓存空间。
那么，我们就来说说分区函数。
分区函数
加载中…
丑陋的实现
回想一下我们前面实现的分区函数：
def partition(arr, low, high):
if low >= high:
return -1
leftPartition = []
rightPartition = []
pivot = arr[low]
for i in range(low + 1, high + 1):
if (arr[i] = high:
return -1
pi = low
li = low + 1
ri = high
while ri >= li:
if arr[li] > arr[pi]:
swap(arr, ri, li)
ri -= 1
else:
li += 1
pi = li – 1
swap(arr, low, pi)
return pi
在这里可以明确告诉大家：这个优雅的分区函数 partitionV2()，和之前那个丑陋的分区函数 partition()，不仅功能相同，而且接口都是完全一样。
先来看输入，这个 partitionV2()函数同样是接受三个参数：
arr：一个用来承载所有待排数字的列表；
low：待排区间的起始下标；
high：待排区间的终止下标。
再来看输出：
本分区函数返回值为 pi：分区完成后轴所在位置的下标；
函数运行完成后，arr 内部元素的顺序已经是分区后的结果了。
接口倒是挺容易看懂的，搞明白 partitionV2()函数体的逻辑了吗？
我们一起来看看这个函数，从代码的「字面」分析，我们很容易看出：
本分区函数内有三个内部标量——pi，li 和 ri，很显然它们都是 arr 的下标，而且这三个变量的初始值分别是待查区域中的第一个、第二个和最后一个元素。这三个变量的值在运行过程中都有可能改变。
代码中调用了之前我们写的 swap() 函数，它是用来交换列表中的元素的。
程序的主题部分是一个 while 循环，在这个循环中发生的操作包括交换元素以及 ri 和 li 的值的变化。
NOTE：在循环中，pi 的值不变。
循环结束后还做了两件事：改变了 pi 的值，交换了一次元素。
要完全明了函数的运作细节，就必须要把 while 循环的过程弄明白——
加载中…
while 循环「里面」到底经历了什么？
为什么经过那么短短几行的代码，我们就把一个待排序区域中原本位于区域头部的元素（「轴」）放到了它最终的目标位置上，还把区域中不比它大的都放到了它之前，而比它大的都放到了它之后？
为什么在 while 循环里只有 li 和 ri 被重新赋值？难道在 while 里 pi 自始至终都指向一个元素？如果是这样，为什么一次迭代中唯一的 swap()操作还总是发生在 arr[li]和 arr[pi]比大小之后？
while 循环之后的 pi = li – 1，以及最后的 swap()，到底是为了达到什么目的呀？
这些问题，你都搞清楚了吗？
如果无须进一步解释，已经都看明白了，那我得说：真棒，手动赞！
但是如果你把每一行符号代码扫了一遍之后，仍然感觉不明就里，也不必着急。本来这个算法就不是很直观。
其实，阅读循环代码，是阅读代码中的一个普遍难点。很多时候看似简单的循环代码，却好像读来读去读不懂，这在学习代码的过程中，是蛮常见的。
这个时候，我们可以用「人肉计算机」法，来辅助阅读代码。具体怎么做呢？请看下一章。