|
大家好，欢迎来到 Crossin的编程教室 ！ 如果你还不懂快速排序，那么希望这篇讲解可以让你理解快排的核心思想。 上次介绍了代码可视化工具pythontutor，并且用快排的代码做了演示。 后来有小伙伴说没太看懂。那今天我们就用pythontutor来详细过一遍这个快排的代码。 快速排序是一种非常常见的排序算法，虽然在实际开发中，你几乎不需要自己去写，但它却是笔试面试的高频问题，甚至“手写快排”已经成为了一个梗。
快排的原理说起来很简单，就是从序列中挑出一个基准的数，比它小的放左边，比它大或相等的放右边。然后对两边的序列再分别采用这个方式进一步划分，直到子序列只剩下一个或没有元素为止。
这种思想叫作分治，就是把一个复杂的问题划分成相同或相似子问题，以此类推，直到子问题可以简单求解。分治在代码上的实现通常会用到递归函数。
quick_sort就是实现快排的递归函数，arr是待排序的列表 递归函数都需要有一个结束条件，不然程序就要死循环到StackOverflow了，这里的结束条件就是序列的长度小于等于1，因为没有元素或只有1个元素的序列不用做任何操作它就是有序的。 当然一开始，我们这个序列是不满足的，于是程序往下走，选取列表第一个元素3为pivot，也就是基准数，然后创建左右两个子列表。接下来就是对第一个元素往后的列表进行遍历，比基准小的（2、1）就加到左列表，相等或大的（7、9、5、8）就加到右列表。
到这里都还比较好理解，然后接下来就是整个代码最核心的一句话了。 这里直接就return返回结果了，结果是什么呢，是把左列表进行快排的结果，加上基准数，再加上右列表进行快排的结果。 看起来好像还挺简单的，可是现在左列表和右列表都还没有排序呢，怎么就能这样加起来呢？ 哎，这就是递归的精妙之处。我们继续结合代码往下走。 单看这行代码的优先级，会先去调用quick_sort(left)拿到返回值，再调用quick_sort(right)拿到返回值，然后再执行列表的+运算，也就是合并列表，最后return返回。 那现在再次进入 quick_sort，参数就成了 left，也就 [2, 1]。虽然这时候人眼一看就知道排序结果应该是 [1, 2]，但程序还是要一步一步来。pivot是2，left 是 [1]，right是空列表。然后继续下一层的递归。这时候，quick_sort([1]) 和 quick_sort([]) 都会触发结束条件了，于是直接返回，返回结果再和刚才这一层的pivot，也就是 [2] 合并在一起，就成了 [1, 2]。然后，它才能返回给再上面一层的函数，也就是我们最外层的quick_sort里面这个quick_sort(left)的结果。
解决了quick_sort(left)，接下来就是quick_sort(right)了，这时参数成了[7,9,5,8]，pivot是7，left是[5]，right是[9,8]。 left因为只有一个元素所以调用后直接返回，但right还要继续往下走，pivot是9，left是[8]，right是[]，再多调用一层，然后返回[8,9]，再跟上一层合并成[5,7,8,9]，返回给最外层。
这时候递归调用的函数全部都返回了，left、pivot、right再加一起，就是最后的结果[1,2,3,5,7,8,9]，返回并输出，程序结束。
快速排序还有其他一些写法，比如不新建子列表，而是在原列表上通过交换元素位置达到划分左右子列表的目的，又比如使用列表里前中后三个元素的中值作为划分的基准数。这些会在一定程度上优化程序的执行效率，但核心的算法原理还是一样的。 作者：Crossin的编程教室 |
|
|
