快速排序（ quick sort ）又称为 分区交换排序（ partition-exchange sort ），是一种非常高效的排序算法，简称 快排 。快排算法也用到了 分治法 思想，它通过对序列进行划分，来降低问题规模。
快排在平均情况下，时间复杂度为 $O(n\log{n})$ ；但在最坏情况下，时间复杂度为 $O(n^2)$ ，好在这种情况不常见。实际上，快排的内部循环对大部分处理器架构更友好，执行效率更高。因此，快排执行速度，通常会明显比其他排序算法更快。
那么，快速排序到底是怎么做的呢？其实也不复杂，主要分为 3 步：
- 从序列中挑选一个元素作为 基准（ pivot ）；
- 根据元素与基准元素的相对大小，将序列进行 划分（ split ）：
- 比基准小的元素排在基准的左边（左子序列）；
- 比基准大的元素排在基准的右边（右子序列，也包括基准相等的部分）；
- 基准元素则位于两者中间；
- 递归执行快速排序算法，分别对左子序列和右子序列进行排序；
序列划分
划分序列，是快排算法中最为关键的一步。那我们就先将这个重点和难点一举拿下！
如果觉得文字描述有点抽象，可以先观看后面的动画，再结合文字理解。
-
挑选一个元素作为划分基准，通常是随机选一个（假设下标为 $p$ ，值为 $pivot$ ）；
-
将选中的基准元素，交换到序列尾部（假设下标为 $last$ ）；
-
用两个变量从剩余元素头尾，分头遍历：
- 变量 $i$ ，初始化为 0 ，指向剩余元素的头部；
- 变量 $j$ ，初始化为 $last-1$ ，指向剩余元素的尾部；
-
循环遍历剩余元素，直到 $i>j$ 时退出循环：
-
遍历时保证，$i$ 左侧元素比基准 $pivot$ 小，$j$ 右侧元素至少跟基准一样大；
-
如果元素 $i$ 值小于基准 $pivot$ ，则自增 $i$ 使其指向下一元素；
-
如果元素 $j$ 值大于等于基准 $pivot$ ，则自减 $j$ 使其指向下一元素；
-
否则意味着元素 $i$ 大于等于基准，而且元素 $j$ 小于基准，这时将两者位置交换，自增 $i$ 并自减 $j$ 使其指向下一元素；
-
循环执行完毕，小于基准的元素均位于 $i$ 左侧，其余元素位于 $j$ 右侧；
- $i$ 和 $j$ 刚好相邻，而且 $i$ 刚好比 $j$ 大 1；
- $i$ 左侧元素均比基准小，因此 $i$ 刚好可以作为基准元素的最终位置；
-
将基准元素从序列尾部，交换到位置 $i$ ，序列划分完毕；
下面这个动画，形象地演示了划分序列的所有步骤，可以多观察几遍，加深理解：
下面是序列划分过程的代码示例，可结合动画和注释进行理解：
快排算法
掌握了序列划分方法后，理解快速排序算法就毫不费劲了，可简单归纳为两步：
- 通过前面介绍的方法，将序列划分为两部分，左子序列比较小，右子序列比较大；
- 递归执行快速排序算法，对两个子序列进行排序；
下面这个动画，很形象地演示了快速排序的过程，有助于加深理解：
下面是快速排序的代码示例，可结合动画和注释进行理解：
效率影响因素
本文开头提过，快排算法最坏情况下时间复杂度为 $O(n^2)$ 。那么，最坏情况通常是怎么发生的呢？请观察下面这个动画，这是一个特例：
在这个例子中，被选中的基准元素刚好就是最小的那个。因此，序列划分完毕后，只包含右子序列，长度为 $n-1$ ，规模几乎没有缩小。序列划分不均，则意味着快排效率将大打折扣。
在极端情况下，每次划分序列时都刚好选到最大或最小值，快排效率便退化为 $O(n^2)$ 。
为了提高快排效率，可以优化划分基准的选择，尽量接近序列的 中位数 。通常可以从序列中随机抽取若干个元素作为样本，然后取样本的中位数作为划分基准。
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
