Java源码解析-DualPivotQuicksort

迷南。 2022-05-28 03:06 207阅读 0赞

# 前言 #

一直都想阅读一些比较深层次的东西，但是自己的水平还没有达到那个层次，所以从比较基础也是比较底层的Java源码下手。

排序应该是使用的比较多，性能比重比较大的算法之一，而快排更是排序中的经典。不论是C++的qsort还是Java的Arrays.sort都是快排实现，我一直很好奇这些语言设计者写出的快排是怎样的，不看不知道，一看吓一跳，果然跟我以前学的快排不一样，我们就来了解一下Java中的快排实现吧。

# JAVA中不同的快排 #

Java在不同版本中对算法进行更改已经不是稀罕事了，对于sort方法也不例外。

## Java1.7之前的快排 ##

在Java1.7之前的快排只是普通的快排，跟我们今天要研究的快排不一样，性能也差了许多，但其中对快排所做的各种优化我们依然是可以学习的。

## Java1.7的快排 ##

Java1.7的快排是一种双轴快排，顾名思义：双轴快排是基于两个轴来进行比较，跟普通的选择一个点来作为轴点的快排是有很大的区别的。算法是由Vladimir Yaroslavskiy在2009年研究出来的，并在2011年发布在了Java1.7。由于Arrays.sort对于数组的排序做了各种各样的优化，并且大多数优化和我们今天要研究的双轴排序无关，所以我们暂且略过，以后有时间研究Arrays源码的时候我们再进行分析。

# 算法分析 #

既然这个算法比之前快排要快，那么肯定有它的巧妙之处，我们来仔细看看吧。

## 算法步骤 ##

1.对于很小的数组（长度小于27），会使用插入排序。  
2.选择两个点P1,P2作为轴心，比如我们可以使用第一个元素和最后一个元素。  
3.P1必须比P2要小，否则将这两个元素交换，现在将整个数组分为四部分：  
（1）第一部分：比P1小的元素。  
（2）第二部分：比P1大但是比P2小的元素。  
（3）第三部分：比P2大的元素。  
（4）第四部分：尚未比较的部分。  
在开始比较前，除了轴点，其余元素几乎都在第四部分，直到比较完之后第四部分没有元素。  
4.从第四部分选出一个元素a\[K\]，与两个轴心比较，然后放到第一二三部分中的一个。  
5.移动L，K，G指向。  
6.重复 4 5 步，直到第四部分没有元素。  
7.将P1与第一部分的最后一个元素交换。将P2与第三部分的第一个元素交换。  
8.递归的将第一二三部分排序。

## 图表演示 ##

![SouthEast][]

注：图片来自Vladimir Yaroslavskiy的论文。

## 算法源码 ##

**\[java\]**  [view plain][]   [copy][view plain]

1.  //对外公开的两个sort方法  
2.  public static void sort(int\[\] a) \{  
3.      sort(a, 0, a.length);  
4.  \}  
5.  public static void sort(int\[\] a, int fromIndex, int toIndex) \{  
6.      rangeCheck(a.length, fromIndex, toIndex);  
7.      dualPivotQuicksort(a, fromIndex, toIndex - 1, 3);  
8.  \}  
9.  //对数组的边界检测  
10. private static void rangeCheck(int length, int fromIndex, int toIndex) \{  
11.     if (fromIndex > toIndex) \{  
12.         throw new IllegalArgumentException("fromIndex > toIndex");  
13.     \}  
14.     if (fromIndex < 0) \{  
15.         throw new ArrayIndexOutOfBoundsException(fromIndex);  
16.     \}  
17.     if (toIndex > length) \{  
18.         throw new ArrayIndexOutOfBoundsException(toIndex);  
19.     \}  
20. \}  
21. //交换数组中两个元素  
22. private static void swap(int\[\] a, int i, int j) \{  
23.     int temp = a\[i\];  
24.     a\[i\] = a\[j\];  
25.     a\[j\] = temp;  
26. \}  
27. /\*\* 
28.  \* 双轴快排的具体实现 
29.  \* @param a     待排序数组 
30.  \* @param left  数组需排序上界 
31.  \* @param right 数组需排序下界 
32.  \* @param div   理解为从何位置取轴 
33.  \*/  
34. private static void dualPivotQuicksort(int\[\] a, int left,int right, int div) \{  
35.     int len = right - left;  
36.     //数组长度如果很小（27），则直接用插入排序对其排序  
37.     if (len < 27) \{  
38.         for (int i = left + 1; i <= right; i++) \{  
39.             for (int j = i; j > left && a\[j\] < a\[j - 1\]; j--) \{  
40.                 swap(a, j, j - 1);  
41.             \}  
42.         \}  
43.         return;  
44.     \}  
45.     //取到位于1/div和div-1/div位置的点，并用他们来做轴  
46.     int third = len / div;  
47.     int m1 = left + third;  
48.     int m2 = right - third;  
49.     if (m1 <= left) \{  
50.         m1 = left + 1;  
51.     \}  
52.     if (m2 >= right) \{  
53.         m2 = right - 1;  
54.     \}  
55.     //确保left是小的，right是大的  
56.     if (a\[m1\] < a\[m2\]) \{  
57.         swap(a, m1, left);  
58.         swap(a, m2, right);  
59.     \}  
60.     else \{  
61.         swap(a, m1, right);  
62.         swap(a, m2, left);  
63.     \}  
64.     // 两个轴  
65.     int pivot1 = a\[left\];  
66.     int pivot2 = a\[right\];  
67.     // 代表比p1小和比p2大的两个指针  
68.     int less = left + 1;  
69.     int great = right - 1;  
70.     // 开始取出less到great之间的未知大小数据，与两个轴比较  
71.     // 并且将数据放入正确的区域后调整各个指针  
72.     for (int k = less; k <= great; k++) \{  
73.         //如果取出的数比p1小，那么直接到less左侧，并且less右移  
74.         if (a\[k\] < pivot1) \{  
75.             swap(a, k, less++);  
76.         \}   
77.         //如果取出的数比p2大，那么首先确定great左侧没有比p2大的数  
78.         //然后与great位置的数字交换，great左移  
79.         //此时，great交换的数字肯定是比p2小或者相等的（首先确定过）  
80.         //那么此时再与p1相比，处理这个数的区间  
81.         else if (a\[k\] > pivot2) \{  
82.             while (k < great && a\[great\] > pivot2) \{  
83.                 great--;  
84.             \}  
85.             swap(a, k, great--);  
86.             if (a\[k\] < pivot1) \{  
87.                 swap(a, k, less++);  
88.             \}  
89.         \}  
90.         //如果这个数比p1大但是比p2小，则不需要交换，只需将k指针右移  
91.     \}  
92.     //将p1与less左侧的第一个数交换  
93.     swap(a, less - 1, left);  
94.     //将p2与great右侧的第一个数交换  
95.     swap(a, great + 1, right);  
96.     // 计算出在两轴大小之间的个数  
97.     int dist = great - less;  
98.     //如果这个数很小（13），那么取轴的点向两边偏  
99.     if (dist < 13) \{  
100.         div++;  
101.     \}  
102.     // 对三个子区间分别排序，因为less-1和great+1是轴，已经排好了序  
103.     // 所以不需要比较  
104.     dualPivotQuicksort(a, left, less - 2, div);  
105.     dualPivotQuicksort(a, great + 2, right, div);  
106.     // 如果在中间区间的数字很多，那么排除掉一些相等的元素再进行排序  
107.     if (dist > len - 13 && pivot1 != pivot2) \{  
108.         for (int k = less; k <= great; k++) \{  
109.             if (a\[k\] == pivot1) \{  
110.                 swap(a, k, less++);  
111.             \}  
112.             else if (a\[k\] == pivot2) \{  
113.                 swap(a, k, great--);  
114.                 if (a\[k\] == pivot1) \{  
115.                     swap(a, k, less++);  
116.                 \}  
117.             \}  
118.         \}  
119.     \}  
120.     // 对中间的区间排序  
121.     if (pivot1 < pivot2) \{  
122.         dualPivotQuicksort(a, less, great, div);  
123.     \}  
124. \}

# 总结 #

双轴排序利用了区间相邻的特性，对原本的快排进行了效率上的提高，很大程度上是利用了数学的一些特性，果然，算法跟数学还是息息相关的吖。

[SouthEast]: /images/20220528/fe6a4ab1f1ac4a9cb8d847a54e25a025.png
[view plain]: https://blog.csdn.net/xjyzxx/article/details/18465661#