偶然注意到的jdk里的排序DualPivotQuicksort

Filed Under: 技术 by admin

Jul.11, 2015

缘起于看某一个类时候注意到的Arrays.copy，以前一直用，却没仔细进去瞅瞅

public static void sort(long[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

DualPivotQuicksort初步看上去是快排的一种，查阅了一下，复杂度是nlogn，但大规模经验数据证明整体性、稳定性不错，引用看到的评论所说:"And this is why we are extremely grateful to the Java Library designers that we don't have to implement our own sorting algorithms, otherwise we'd all be using bubble sort ;-) "

附上看到的What's the difference of dual pivot quick sort and quick sort?
原文地址http://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort

I find this in the java doc.

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.
Then I find this in the google search result. Thoery of quick sort algorithm:

Pick an element, called a pivot, from the array.
Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot element is in its final position.
Recursively sort the sub-array of lesser elements and the sub-array of greater elements.
In comparison,dual-pivot quick sort:
请输入图片描述
For small arrays (length < 17), use the Insertion sort algorithm.
Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.
P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
part I with indices from left+1 to L–1 with elements, which are less than P1,
part II with indices from L to K–1 with elements, which are greater or equal to P1 and less or equal to P2,
part III with indices from G+1 to right–1 with elements greater than P2,
part IV contains the rest of the elements to be examined with indices from K to G.
The next element a[K] from the part IV is compared with two pivots P1 and P2, and placed to the corresponding part I, II, or III.
The pointers L, K, and G are changed in the corresponding directions.
The steps 4 - 5 are repeated while K ≤ G.
The pivot element P1 is swapped with the last element from part I, the pivot element P2 is swapped with the first element from part III.
The steps 1 - 7 are repeated recursively for every part I, part II, and part III.