算法：再谈快速排序

1. 基本原理

快速排序由 Tony Hoare 发表于 1961 年。是一种分治算法，基本步骤：

1. 从数组中选择一个基准元素（pivot）；
2. 分区：重排数组元素，使得小于 pivot 的值都在 pivot 左侧，大于 pivot 的值都在pivot 右侧（与 pivot 相等的值放在哪边都行），分区完成后，pivot 所处的位置就是最终位置。
3. 对分区后的左右两部分子数组，递归进行上述操作。（递归终止条件：数组为空或只有一个元素，无需排序。）

特别注意：不同的 pivot 选择策略、不同的分区策略，都会对快排性能产生影响。

时间复杂度

最坏：O(n^2) 、平均：O(nlogn)

下面介绍快速排序的几种不同实现

2. 实现1：Lomuto 分区策略

Nico Lomuto 分区策略，出自《算法导论》，虽然效率不算高，但容易理解。

图：Lomuto 分区策略

3. 实现2：Lomuto 变形

跟Lomuto差不多

动画

代码示例

4. 实现3：Hoare 分区策略

Hoare 分区规则是快速排序作者最原始的规则，它比Lomuto分区规则更高效。而且也不是简单的选择开头或结尾元素作为 pivot，最大限度避免算法退化到 O(n^2)。

图：Hoare 分区策略

5. 实现4：DNF（荷兰旗）分区策略

假设数组中所有元素都相同（极端场景）：

• Lomuto 分区策略，每次分区后，左侧分区为空，右侧只减少一个元素（除去pivot），直接退化为 O(n^2)；
• Hoare 分区策略，每次分区后，左右两侧分区是平衡的，但会有很多不必要的元素交换，也是在浪费时间；

DNF（Dutch national flag，荷兰旗）算法就是这类问题一种解，将数组分3个区，“<pivot”区、“=pivot区”、“>pivot区”。由于“=pivot区”实际已经有序，所以只有“<pivot区”和“>pivot区”参与递归排序即可。

Dutch national flag（DNF） 算法

叕是 Edsger Dijkstra

这货提出来的

某盒子中有n个球，每个球的颜色可以是红、蓝、白，现在要求把球按照红、蓝、白的顺序摆放。这个问题叫做荷兰旗问题（荷兰旗由红、蓝、白三色组成）

图：DNF 分区策略

5. 实现4：DualPivotQuickSort

JDK7 对【基本数据类型】数组的

默认排序算法是

DualPivotQuickSort

是快速排序的超豪华版本

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

图：JDK，Arrays源码节选