# 快速排序
作者: 王振州 时间: 2020-12-10
快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法, 通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列, 并且会不断重复这个步骤直到所有数据都是有序的
# 1 核心思想
基础的快速排序算法的思想就是找到基准值的位置
# 2 第一步: 选择一个值作为基准值
最简单的方法是选择待排序区间的头部元素作为基准值, 如下图, 选择3作为基准值
# 3 第二步: 将小于基准值的元素放在基准值的前面, 将大于基准值的元素放在基准值的后面
这一步通常被叫做 partition 操作，中文直译过来就是分割操作，也就是用基准值将原数组分割成前后两部分。
理解了 partition 操作的目的以后，我们再来讨论它具体是怎么做的。partition 操作简单来说，就是空出一个位置，反复地前后调换元素。这该怎么理解呢？首先，你要理解一点，当我们选择了基准值以后，原先基准值的位置就相当于被空出来了，也就是说数组的第一位是空着的。
如果第一位是空的，那剩下的事儿就好办了。我们借助这个空位，将后面小于基准值的元素放到前面的空位上，这样后面就空出一位了。然后，我们再将前面大于基准值的元素放到后面这个空位上。就这样交替进行，直到空位前面的值都小于基准值，空位后面的值都大于基准值为止。过程如下图所示：
# 4 第三步: 对基准值的左右两侧，递归地进行第一步和第二步
我们要分别对 4、1、5 和 8、14、9、11、7 这两部分，再做选择基准值、找基准值位置和递归这三步。由于每次 partition 操作中，我们都会确定一个值，也就是基准值的正确位置，所以，经过有限次递归操作以后，整个数组也就变成了一个有序数组。当然，像上面这样的描述是不严谨的，但它确实是正确的。而且严谨的证明过程太过复杂，我就不详细来说了，如果你还记得数学归纳法和递归程序之间的关系，可以试着用它来证明快速排序算法的正确性。