双基准快速排序（Dual-Pivot Quicksort）（转）

课本上常见的快速排序都是选择一个枢纽元（Pivot），基于这个枢纽元从前后双向扫描分成大于枢纽元和小于枢纽元的。而从JDK 7开始，java.util.Arrays.sort()使用双基准快速排序（Dual-Pivot Quicksort）作为实现。

传统快速排序：

1. 选择枢纽元pivot,有很多种选法，但都只有一个。
2. 基于枢纽元分成大于和小于的两部分，并且枢纽元放到最终的位置。
3. 递归排序大于和小于的两部分。

双基准快速排序：

1. 对于长度小于17的数组使用插入排序(常见优化步骤，传统快排也有应用)。
2. 选择两个枢纽元p1,p2，一般选择起始元素a[left]和末尾元素a[right]（有其他选取方式）。
3. 假设p1<p2，如果不是就交换。
4. 基于这p1,p2将整个数组分成三部分，<p1的,p1<&<p2的,>p2的。
5. 递归排序这三个部分。

其中4这个步骤是采用单向扫描，leetcode上的Sort Colors这题一般就是采用同样的方法分成三部分。
https://oj.leetcode.com/problems/sort-colors/

详细的可以参考下面论文，里面有详细的细节以及算法实现。

Reference：

DualPivotQuicksort.pdf

双基准快速排序（Dual-Pivot Quicksort）（转）

原文：http://www.cnblogs.com/xymqx/p/4361947.html