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

灰太狼 2022-07-15 01:07 170阅读 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. /\*
16.  \* Traditional (without sentinel) insertion sort,
17.  \* optimized for server VM, is used in case of
18.  \* the leftmost part.
19.  \*/
20. **for** (**int** i = left, j = i; i < right; j = ++i) \{ 
21. **int** ai = a\[i + 1\]; 
22. **while** (ai < a\[j\]) \{ 
23.  a\[j + 1\] = a\[j\]; 
24. **if** (j-- == left) \{ 
25. **break**; 
26.  \} 
27.  \} 
28.  a\[j + 1\] = ai; 
29.  \} 
30.  \} **else** \{ 
31. /\*
32.  \* Skip the longest ascending sequence.
33.  \*/
34. **do** \{ 
35. **if** (left >= right) \{ 
36. **return**; 
37.  \} 
38.  \} **while** (a\[++left\] >= a\[left - 1\]); 
39. 
40. /\*
41.  \* Every element from adjoining part plays the role
42.  \* of sentinel, therefore this allows us to avoid the
43.  \* left range check on each iteration. Moreover, we use
44.  \* the more optimized algorithm, so called pair insertion
45.  \* sort, which is faster (in the context of Quicksort)
46.  \* than traditional implementation of insertion sort.
47.  \*/
48. **for** (**int** k = left; ++left <= right; k = ++left) \{ 
49. **int** a1 = a\[k\], a2 = a\[left\]; 
50. 
51. **if** (a1 < a2) \{ 
52.  a2 = a1; a1 = a\[left\]; 
53.  \} 
54. **while** (a1 < a\[--k\]) \{ 
55.  a\[k + 2\] = a\[k\]; 
56.  \} 
57.  a\[++k + 1\] = a1; 
58. 
59. **while** (a2 < a\[--k\]) \{ 
60.  a\[k + 1\] = a\[k\]; 
61.  \} 
62.  a\[k + 1\] = a2; 
63.  \} 
64. **int** last = a\[right\]; 
65. 
66. **while** (last < a\[--right\]) \{ 
67.  a\[right + 1\] = a\[right\]; 
68.  \} 
69.  a\[right + 1\] = last; 
70.  \} 
71. **return**; 
72.  \}

当小于47个时，使用插入排序。

参数a为需要排序的数组，left代表需要排序的数组区间中最左边元素的索引，right代表区间中最右边元素的索引，leftmost代表该区间是否是数组中最左边的区间。举个例子：

数组：\[2, 4, 8, 5, 6, 3, 0, -3, 9\]可以分成三个区间（2, 4, 8）\{5, 6\}<3, 0, -3, 9>

对于（）区间，left=0, right=2, leftmost=true

对于 \{\}区间， left=3, right=4, leftmost=false,同理可得<>区间的相应参数

当区间长度小于47时，该方法会采用插入排序；否则采用快速排序。

1、 当leftmost为true时，它会采用传统的插入排序（traditional insertion sort），代码也较简单，其过程类似打牌时抓牌插牌。

2、当leftmost为false时，它采用一种新型的插入排序（pair insertion sort），改进之处在于每次遍历前面已排好序的数组需要**插入两个元素**，而传统插入排序在遍历过程中只需要为一个元素找到合适的位置插入。对于插入排序来讲，其关键在于为待插入元素找到合适的插入位置，为了找到这个位置，需要遍历之前已经排好序的子数组，所以对于插入排序来讲，整个排序过程中其遍历的元素个数决定了它的性能。很显然，**每次遍历插入两个元素可以减少排序过程中遍历的元素个数**。

为左边区间时，pair insertion sort在左边元素比较大时，会越界。

#### 双枢轴快速排序 ####

对于快速排序来讲，其每一次递归所做的是使需要排序的子区间变得**更加有序**，而不是绝对有序；所以对于快速排序来说，其性能决定于每次递归操作使待排序子区间变得有序的程度，另一个决定因素当然就是递归次数。快速排序使子区间变得相对有序的关键是pivot,所以我们优化的方向也应该在于pivot,那就增加pivot的个数吧，而且我们可以发现，增加pivot的个数，对递归次数并不会有太大影响，有时甚至可以使递归次数减少。和insert sort类似的问题就是，pivot增加为几个呢？很显然，pivot的值也不能太大；记住，任何优化都是**有代价的**，而增加pivot的代价就隐藏在每次交换元素的位置过程中。

下面是寻找枢轴的过程：

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

1.  // Inexpensive approximation of length / 7，1/7=1/8+1/32
2.  **int** seventh = (length >> 3) + (length >> 6) + 1; 
3.  
4.  /\*
5.   \* Sort five evenly spaced elements around (and including) the
6.   \* center element in the range. These elements will be used for
7.   \* pivot selection as described below. The choice for spacing
8.   \* these elements was empirically determined to work well on
9.   \* a wide variety of inputs.
10.  \*/
11. **int** e3 = (left + right) >>> 1; // The midpoint
12. **int** e2 = e3 - seventh; 
13. **int** e1 = e2 - seventh; 
14. **int** e4 = e3 + seventh; 
15. **int** e5 = e4 + seventh; 
16. 
17. // Sort these elements using insertion sort
18. **if** (a\[e2\] < a\[e1\]) \{ **int** t = a\[e2\]; a\[e2\] = a\[e1\]; a\[e1\] = t; \} 
19. 
20. **if** (a\[e3\] < a\[e2\]) \{ **int** t = a\[e3\]; a\[e3\] = a\[e2\]; a\[e2\] = t; 
21. **if** (t < a\[e1\]) \{ a\[e2\] = a\[e1\]; a\[e1\] = t; \} 
22. \} 
23. **if** (a\[e4\] < a\[e3\]) \{ **int** t = a\[e4\]; a\[e4\] = a\[e3\]; a\[e3\] = t; 
24. **if** (t < a\[e2\]) \{ a\[e3\] = a\[e2\]; a\[e2\] = t; 
25. **if** (t < a\[e1\]) \{ a\[e2\] = a\[e1\]; a\[e1\] = t; \} 
26.  \} 
27. \} 
28. **if** (a\[e5\] < a\[e4\]) \{ **int** t = a\[e5\]; a\[e5\] = a\[e4\]; a\[e4\] = t; 
29. **if** (t < a\[e3\]) \{ a\[e4\] = a\[e3\]; a\[e3\] = t; 
30. **if** (t < a\[e2\]) \{ a\[e3\] = a\[e2\]; a\[e2\] = t; 
31. **if** (t < a\[e1\]) \{ a\[e2\] = a\[e1\]; a\[e1\] = t; \} 
32.  \} 
33.  \} 
34. \} 
35. 
36. // Pointers
37. **int** less = left; // The index of the first element of center part
38. **int** great = right; // The index before the first element of right part
39. 
40. **if** (a\[e1\] != a\[e2\] && a\[e2\] != a\[e3\] && a\[e3\] != a\[e4\] && a\[e4\] != a\[e5\]) \{ 
41. /\*
42.  \* Use the second and fourth of the five sorted elements as pivots.
43.  \* These values are inexpensive approximations of the first and
44.  \* second terciles of the array. Note that pivot1 <= pivot2.
45.  \*/
46. **int** pivot1 = a\[e2\]; 
47. **int** pivot2 = a\[e4\]; 
48. 
49. /\*
50.  \* The first and the last elements to be sorted are moved to the
51.  \* locations formerly occupied by the pivots. When partitioning
52.  \* is complete, the pivots are swapped back into their final
53.  \* positions, and excluded from subsequent sorting.
54.  \*/
55.  a\[e2\] = a\[left\]; 
56.  a\[e4\] = a\[right\];

1. pivot的选取方式是将数组分成近视等长的七段，而这七段其实是被5个元素分开的，将这5个元素从小到大排序，取出第2个和第4个，分别作为pivot1和pivot2。

**注意：当这个5元素都互不相等时，才采用双枢轴快速排序！**

2. Pivot选取完之后，分别从左右两端向中间遍历，左边遍历停止的条件是遇到一个大于等于pivot1的值，并把那个位置标记为less;右边遍历的停止条件是遇到一个小于等于pivot2的值，并把那个位置标记为great

3. 然后从less位置向后遍历，遍历的位置用k表示，会遇到以下几种情况：

a. k位置的值比pivot1小，那就交换k位置和less位置的值，并是less的值加1;这样就使得less位置左边的值都小于pivot1,而less位置和k位置之间的值大于等于pivot1

b. k位置的值大于pivot2,那就从great位置向左遍历，遍历停止条件是遇到一个小于等于pivot2的值，假如这个值小于pivot1,就把这个值写到less位置，把less位置的值写道k位置，把k位置的值写道great位置，最后less++,great--;加入这个值大于等于pivot1,就交换k位置和great位置，之后great--。

4. 完成上述过程之后，带排序的子区间就被分成了三段（pivot2），最后分别对这三段采用递归就行了。

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

1.  /\*
2.   \* Skip elements, which are less or greater than pivot values.
3.   \*/
4.  **while** (a\[++less\] < pivot1); 
5.  **while** (a\[--great\] > pivot2); 
6.  
7.  /\*
8.   \* Partitioning:
9.   \*
10.  \* left part center part right part
11.  \* +--------------------------------------------------------------+
12.  \* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
13.  \* +--------------------------------------------------------------+
14.  \* ^ ^ ^
15.  \* | | |
16.  \* less k great
17.  \*
18.  \* Invariants:
19.  \*
20.  \* all in (left, less) < pivot1
21.  \* pivot1 <= all in \[less, k) <= pivot2
22.  \* all in (great, right) > pivot2
23.  \*
24.  \* Pointer k is the first index of ?-part.
25.  \*/
26.  outer: 
27. **for** (**int** k = less - 1; ++k <= great; ) \{ 
28. **int** ak = a\[k\]; 
29. **if** (ak < pivot1) \{ // Move a\[k\] to left part
30.  a\[k\] = a\[less\]; 
31. /\*
32.  \* Here and below we use "a\[i\] = b; i++;" instead
33.  \* of "a\[i++\] = b;" due to performance issue.
34.  \*/
35.  a\[less\] = ak; 
36.  \++less; 
37.  \} **else****if** (ak > pivot2) \{ // Move a\[k\] to right part
38. **while** (a\[great\] > pivot2) \{ 
39. **if** (great-- == k) \{ 
40. **break** outer; 
41.  \} 
42.  \} 
43. **if** (a\[great\] < pivot1) \{ // a\[great\] <= pivot2
44.  a\[k\] = a\[less\]; 
45.  a\[less\] = a\[great\]; 
46.  \++less; 
47.  \} **else** \{ // pivot1 <= a\[great\] <= pivot2
48.  a\[k\] = a\[great\]; 
49.  \} 
50. /\*
51.  \* Here and below we use "a\[i\] = b; i--;" instead
52.  \* of "a\[i--\] = b;" due to performance issue.
53.  \*/
54.  a\[great\] = ak; 
55.  \--great; 
56.  \} 
57.  \} 
58. 
59. // Swap pivots into their final positions
60.  a\[left\] = a\[less - 1\]; a\[less - 1\] = pivot1; 
61.  a\[right\] = a\[great + 1\]; a\[great + 1\] = pivot2; 
62. 
63. // Sort left and right parts recursively, excluding known pivots
64.  sort(a, left, less - 2, leftmost); 
65.  sort(a, great + 2, right, **false**);

上述的代码不包含递归中间的数，当中间的数过于多时，会作出下面举动：

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

1.  /\*
2.   \* If center part is too large (comprises > 4/7 of the array),
3.   \* swap internal pivot values to ends.
4.   \*/
5.  **if** (less < e1 && e5 < great) \{ 
6.  /\*
7.   \* Skip elements, which are equal to pivot values.
8.   \*/
9.  **while** (a\[less\] == pivot1) \{ 
10.  \++less; 
11.  \} 
12. 
13. **while** (a\[great\] == pivot2) \{ 
14.  \--great; 
15.  \} 
16. 
17. /\*
18.  \* Partitioning:
19.  \*
20.  \* left part center part right part
21.  \* +----------------------------------------------------------+
22.  \* | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
23.  \* +----------------------------------------------------------+
24.  \* ^ ^ ^
25.  \* | | |
26.  \* less k great
27.  \*
28.  \* Invariants:
29.  \*
30.  \* all in (\*, less) == pivot1
31.  \* pivot1 < all in \[less, k) < pivot2
32.  \* all in (great, \*) == pivot2
33.  \*
34.  \* Pointer k is the first index of ?-part.
35.  \*/
36.  outer: 
37. **for** (**int** k = less - 1; ++k <= great; ) \{ 
38. **int** ak = a\[k\]; 
39. **if** (ak == pivot1) \{ // Move a\[k\] to left part
40.  a\[k\] = a\[less\]; 
41.  a\[less\] = ak; 
42.  \++less; 
43.  \} **else****if** (ak == pivot2) \{ // Move a\[k\] to right part
44. **while** (a\[great\] == pivot2) \{ 
45. **if** (great-- == k) \{ 
46. **break** outer; 
47.  \} 
48.  \} 
49. **if** (a\[great\] == pivot1) \{ // a\[great\] < pivot2
50.  a\[k\] = a\[less\]; 
51. /\*
52.  \* Even though a\[great\] equals to pivot1, the
53.  \* assignment a\[less\] = pivot1 may be incorrect,
54.  \* if a\[great\] and pivot1 are floating-point zeros
55.  \* of different signs. Therefore in float and
56.  \* double sorting methods we have to use more
57.  \* accurate assignment a\[less\] = a\[great\].
58.  \*/
59.  a\[less\] = pivot1; 
60.  \++less; 
61.  \} **else** \{ // pivot1 < a\[great\] < pivot2
62.  a\[k\] = a\[great\]; 
63.  \} 
64.  a\[great\] = ak; 
65.  \--great; 
66.  \} 
67.  \} 
68.  \} 
69. 
70. // Sort center part recursively
71.  sort(a, less, great, **false**);

就是当中间的数超过4/7的时候，按照划分应该很平均才对，所以猜想中间的元素有很多等于pivot1和pivot2的数(划分的时候等于的数放在中间)，会设法减少中间的数，就是把中间的等于pivot1的数放在前方，把等于pivot的数放在后方。

这个做法类似单枢轴快速排序的时候，作为枢轴的元素也有很多相同的，所以在这个时候，应该跳过这些相同元素来进行快速排序。减少递归。

这个做法就相当于再次划分中间的区域，相当于一共根据两个枢轴划分成了5种(多了两种等于p1和p2的)。对其余3种递归。

#### 单枢轴快速排序 ####

当5个元素有相当的时候，假定现在的情况是数组中有很多相同的元素。

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

1.  \} **else** \{ // Partitioning with one pivot
2.  /\*
3.   \* Use the third of the five sorted elements as pivot.
4.   \* This value is inexpensive approximation of the median.
5.   \*/
6.  **int** pivot = a\[e3\]; 
7.  
8.  /\*
9.   \* Partitioning degenerates to the traditional 3-way
10.  \* (or "Dutch National Flag") schema:
11.  \*
12.  \* left part center part right part
13.  \* +-------------------------------------------------+
14.  \* | < pivot | == pivot | ? | > pivot |
15.  \* +-------------------------------------------------+
16.  \* ^ ^ ^
17.  \* | | |
18.  \* less k great
19.  \*
20.  \* Invariants:
21.  \*
22.  \* all in (left, less) < pivot
23.  \* all in \[less, k) == pivot
24.  \* all in (great, right) > pivot
25.  \*
26.  \* Pointer k is the first index of ?-part.
27.  \*/
28. **for** (**int** k = less; k <= great; ++k) \{ 
29. **if** (a\[k\] == pivot) \{ 
30. **continue**; 
31.  \} 
32. **int** ak = a\[k\]; 
33. **if** (ak < pivot) \{ // Move a\[k\] to left part
34.  a\[k\] = a\[less\]; 
35.  a\[less\] = ak; 
36.  \++less; 
37.  \} **else** \{ // a\[k\] > pivot - Move a\[k\] to right part
38. **while** (a\[great\] > pivot) \{ 
39.  \--great; 
40.  \} 
41. **if** (a\[great\] < pivot) \{ // a\[great\] <= pivot
42.  a\[k\] = a\[less\]; 
43.  a\[less\] = a\[great\]; 
44.  \++less; 
45.  \} **else** \{ // a\[great\] == pivot
46. /\*
47.  \* Even though a\[great\] equals to pivot, the
48.  \* assignment a\[k\] = pivot may be incorrect,
49.  \* if a\[great\] and pivot are floating-point
50.  \* zeros of different signs. Therefore in float
51.  \* and double sorting methods we have to use
52.  \* more accurate assignment a\[k\] = a\[great\].
53.  \*/
54.  a\[k\] = pivot; 
55.  \} 
56.  a\[great\] = ak; 
57.  \--great; 
58.  \} 
59.  \} 
60. 
61. /\*
62.  \* Sort left and right parts recursively.
63.  \* All elements from center part are equal
64.  \* and, therefore, already sorted.
65.  \*/
66.  sort(a, left, less - 1, leftmost); 
67.  sort(a, great + 1, right, **false**); 
68. \}

**注意：这是个改进的单枢轴快速排序。这个时候也是3个指针的算法。因为，这个算法就像是分成3类，一类小于枢轴，一类大于枢轴，一类等于枢轴。只用对左右两种进行递归。**

[.NET]: http://lib.csdn.net/base/dotnet
[Link 1]: http://lib.csdn.net/base/datastructure
[SouthEast]: /images/20220715/561096623f0c4f849efddd64d0e81946.png
[SouthEast 1]: /images/20220715/612dd658a45a4d69af19f44af2a97a9d.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