Jdk 1.7.0_17中提供的默认的排序算法

水深无声 2022-07-15 01:07 126阅读 0赞

http://blog.csdn.net/lingzhm/article/details/45022385

参考自：论文，Dual-Pivot Quicksort algorithm ，by Vladimir Yaroslavskiy。

http://www.sytarena.com/javajswz/20140217/1329.html

转载自：http://blog.csdn[.NET][]/jy3161286/article/details/23361191?utm\_source=tuicool

DualPivotQuicksort是JDK1.7开始的采用的快速排序[算法][Link 1]。

一般的快速排序采用一个枢轴来把一个数组划分成两半，然后递归之。

大量经验数据表面，采用两个枢轴来划分成3份的算法更高效，这就是DualPivotQuicksort。

### 算法思想 ###

选出两个枢轴P1和P2，需要3个指针L,K,G。

3个指针的作用如下图：

![SouthEast][]

算法为以下的步骤：

1、小于27的数组，使用插入排序(或47)。

2、选择枢轴P1和P2。(假设使用数组头和尾)。

3、P1需要小于P2，否者交换。

现在数组被分成4份，left到L的小于P1的数，L到K的大于P1小于P2的数，G到rigth的大于P2的数，待处理的K到G的中间的数(逐步被处理到前3个区域中)。

4、L从开始初始化直至不小于P1，K初始化为L-1，G从结尾初始化直至不大于P2。K是主移动的指针，来一步一步吞噬中间区域。

\*\*\*\*当大于P1小于P2，K++。

\*\*\*\*当小于P1，交换L和K的数，L++,K++。

\*\*\*\*当大于P2，如果G的数小于P1，把L上的数放在K上，把G的数放在L上，L++，再把K以前的数放在G上，G--，K++，完成一次L,K,G的互相交换。否则交换K和G，并G--，K++。

5、递归4。

6、交换P1到L-1上。交换P2到G+1上。

7、递归之。

### JDK源码 ###

流程图：

![SouthEast 1][]

#### TimSort ####

直接调用的sort第一级：

**\[java\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **public****static****void** sort(**int**\[\] a, **int** left, **int** right) \{ 
2.  // Use Quicksort on small arrays
3.  **if** (right - left < QUICKSORT\_THRESHOLD) \{ //门限为286
4.   sort(a, left, right, **true**); 
5.  **return**; 
6.   \} 
7.  
8.  /\*
9.   \* Index run\[i\] is the start of i-th run
10.  \* (ascending or descending sequence).
11.  \*/
12. **int**\[\] run = **new****int**\[MAX\_RUN\_COUNT + 1\]; 
13. **int** count = 0; run\[0\] = left; 
14. 
15. // Check if the array is nearly sorted
16. **for** (**int** k = left; k < right; run\[count\] = k) \{ 
17. **if** (a\[k\] < a\[k + 1\]) \{ // ascending
18. **while** (++k <= right && a\[k - 1\] <= a\[k\]); 
19.  \} **else****if** (a\[k\] > a\[k + 1\]) \{ // descending
20. **while** (++k <= right && a\[k - 1\] >= a\[k\]); 
21. **for** (**int** lo = run\[count\] - 1, hi = k; ++lo < --hi; ) \{ 
22. **int** t = a\[lo\]; a\[lo\] = a\[hi\]; a\[hi\] = t; 
23.  \} 
24.  \} **else** \{ // equal
25. **for** (**int** m = MAX\_RUN\_LENGTH; ++k <= right && a\[k - 1\] == a\[k\]; ) \{ 
26. **if** (--m == 0) \{ 
27.  sort(a, left, right, **true**); 
28. **return**; 
29.  \} 
30.  \} 
31.  \} 
32. 
33. /\*
34.  \* The array is not highly structured,
35.  \* use Quicksort instead of merge sort.
36.  \*/
37. **if** (++count == MAX\_RUN\_COUNT) \{ 
38.  sort(a, left, right, **true**); 
39. **return**; 
40.  \} 
41.  \} 
42. 
43. // Check special cases
44. **if** (run\[count\] == right++) \{ // The last run contains one element
45.  run\[++count\] = right; 
46.  \} **else****if** (count == 1) \{ // The array is already sorted
47. **return**; 
48.  \} 
49. 
50. /\*
51.  \* Create temporary array, which is used for merging.
52.  \* Implementation note: variable "right" is increased by 1.
53.  \*/
54. **int**\[\] b; **byte** odd = 0; 
55. **for** (**int** n = 1; (n <<= 1) < count; odd ^= 1); 
56. 
57. **if** (odd == 0) \{ 
58.  b = a; a = **new****int**\[b.length\]; 
59. **for** (**int** i = left - 1; ++i < right; a\[i\] = b\[i\]); 
60.  \} **else** \{ 
61.  b = **new****int**\[a.length\]; 
62.  \} 
63. 
64. // Merging
65. **for** (**int** last; count > 1; count = last) \{ 
66. **for** (**int** k = (last = 0) + 2; k <= count; k += 2) \{ 
67. **int** hi = run\[k\], mi = run\[k - 1\]; 
68. **for** (**int** i = run\[k - 2\], p = i, q = mi; i < hi; ++i) \{ 
69. **if** (q >= hi || p < mi && a\[p\] <= a\[q\]) \{ 
70.  b\[i\] = a\[p++\]; 
71.  \} **else** \{ 
72.  b\[i\] = a\[q++\]; 
73.  \} 
74.  \} 
75.  run\[++last\] = hi; 
76.  \} 
77. **if** ((count & 1) != 0) \{ 
78. **for** (**int** i = right, lo = run\[count - 1\]; --i >= lo; 
79.  b\[i\] = a\[i\] 
80.  ); 
81.  run\[++last\] = right; 
82.  \} 
83. **int**\[\] t = a; a = b; b = t; 
84.  \} 
85. \}

1、当小于286时，直接使用双枢轴快速排序。

2、大于286时，先使用TimSort的思想，找出正序或者倒序的数(run的栈)，然后合并各个run，最后完成TimSort。

3、在找出run的时候，找出的run个数大于67时，即认为它是一个比较乱序的数组，就直接采用双枢轴快速排序。

#### 双元素插入排序 ####

下面看看双枢轴快速排序的实现(代码太长，分解之)：

**\[java\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  /\*\*
2.   \* Sorts the specified range of the array by Dual-Pivot Quicksort.
3.   \*
4.   \* @param a the array to be sorted
5.   \* @param left the index of the first element, inclusive, to be sorted
6.   \* @param right the index of the last element, inclusive, to be sorted
7.   \* @param leftmost indicates if this part is the leftmost in the range
8.   \*/
9.  **private****static****void** sort(**int**\[\] a, **int** left, **int** right, **boolean** leftmost) \{ 
10. **int** length = right - left + 1; 
11. 
12. // Use insertion sort on tiny arrays
13. **if** (length < INSERTION\_SORT\_THRESHOLD) \{ //47个
14. **if** (leftmost) \{ 
15. /\*<li style="border-top: none; border-right: none; border-bottom: none; border-left: 3px solid rgb(108, 226, 108); border-image: initial; list-style-type: decimal-leading-zero; list-style-image: initial; background-color: rgb(248, 248, 248); line-he

[.NET]: http://lib.csdn.net/base/dotnet
[Link 1]: http://lib.csdn.net/base/datastructure
[SouthEast]: /images/20220715/5647ca11f6b146798a49505a9eb47e1a.png
[SouthEast 1]: /images/20220715/05d52ef5afb84b8a8babbfd3e32838be.png
[view plain]: http://blog.csdn.net/jy3161286/article/details/23361191?utm_source=tuicool#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/285347
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/285347/fork