双基准快速排序 Dual-Pivot Quicksort

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

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

—update JDK7使用双基准快速排序来排序基本元素，针对对象用TimSort 

1
2
3
4
5
6
7
8
9
public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0); 
}
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested) //java -Djava.util.Arrays.useLegacyMergeSort=true 这个是运行时配置的
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

传统快速排序：

  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