快速排序

(图片来自 快速排序 - 维基百科

思路

快速排序(简称「快排」)同样是基于分治法(divide and conquer)来设计的,其算法步骤如下:

  1. 从待排序数组中挑出一个元素,称为「基准」(pivot)。
  2. 对数组进行分割(partition),小于 pivot 的数字放在 pivot 前面,大于的放在后面,相等的两边都能放。
  3. 在 pivot 分割开的两个部分递归地执行第 1、2 步(即挑 pivot、分割)。

那么问题来了,怎么选 pivot?事实上,选 pivot 的方法对排序的时间性能有决定性影响

TODO

分析

  • 先来看看 维基百科 怎么说的:

    在平均状况下,排序 $n$ 个项目要 $O(n \log n)$ 次比较。在最坏状况下需要 $O(n^2)$ 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

  • 快排的平均、最优时间复杂度都是 $O(n \log n)$,而最坏时间复杂度为 $O(n^2)$。
  • 空间复杂度为 $O(\log n)$。
  • 算法不稳定。

实现

见《🔢 排序算法 00. 代码实现》(本博客)。