QuickSort学习之快排算法的若干实现方法

快速排序

介绍:分治排序算法,以一个特定元素为分界,划分成两个子数组,两个子数组有序时整个数组就有序

quicksort

普通写法(递归调用)

快排分为两部分:

  • 分片(划分)
    找到一个值,根据这个值将数组分为两个子数组
    最初默认使用数组最左边元素为分界值
  • 排序
    逐渐是子数组排序,从而整个数组是有序的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 分片, 分为两片<v 与>v
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable v = a[lo];
while (true) {
while (less(a[++i], v)) if (i == hi) break;
while (less(v,a[--j])) if(j == lo) break;
if (i>=j) break;
exchange(a,i,j);
}
exchange(a,j,lo);
return j;
}
// 排序
private static void sort(Comparable[] a ,int lo, int hi){
if (hi <= lo) return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
// 对外使用接口
public static void sort(Comparable[] a){
StdRandom.shuffle(a); // 使数组乱序,快排更高效
sort(a,0,a.length-1);
}

优化

三向切分: 对重复值快速排序的优化

原理:

quick3way

优化策略:

  • 将数组分为三块
  • (a[i] < v) a[lt]与a[i]交换 i\lt +1
  • (a[i] > v) a[gt]与a[i] 交换 gt-1
  • (a[i] = v) i+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void Quick3Way(Comparable[] a, int lo, int hi) {
if (lo >= hi) return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo];
while (i <= gt) {
int cmp = v.compareTo(a[i]);
if (cmp > 0) exchange(a, i++, lt++);
else if (cmp < 0) exchange(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
Quick3Way(a, lo, lt - 1);
Quick3Way(a, gt + 1, hi);
assert isSorted(a, lo, hi);
}

QUICKX(快排优化) 原理

介绍
示意图

文字描述
Implement an entropy-optimal sort QuickX.java based on keeping equal keys at both the left and right ends of the subarray. Maintain indices p and q such that a[lo..p-1] that a[q+1..hi] are all equal to a[lo], an index i such that a[p..i-1] are all less than a[lo] and an index j such that a[j+1..q] are all greater than a[lo]. Add to the inner partitioning loop code to swap a[i] with a[p] (and increment p) if it is equal to v and to swap a[j] with a[q] (and decrement q) if it is equal to v before the usual comparisons of a[i] and a[j] with v.
After the partitioning loop has terminated, add code to swap the equal keys into position.
论文链接

优化策略

  • 小数组使插入排序
  • [找到合适的点]使用三分法找到支点pivot(根据不同数组规模采用不同的排序策略)
  • 排序规则
    • 将相等的值放两边 即a[lo…p-1]==alo a[q+1…hi]=alo
    • a[p….i-1] < v
    • a[j+1….q] > v

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 主要代码
private static void QuickX(Comparable[] a, int low, int high) {
int n = high - low + 1;
// 不同规模的排序使用不同的排序策略,选择不同的中心轴
if (n < INSERTION_SORT_CUTOFF) { // 使用插入排序的数组规模是7
insertionSort(a, low, high);
return;
} else if (n < MEDIAN_OF_3_CUTOFF) { // MEDIAN_OF_3_CUTOFF==40
// 轴点位于a[low]
int m = median3(a, low, low + n / 2, high);
exchange(a, m, low);
} else {
// 分为9个点,选出中间点
int eps = n / 8;
int mid = low + n / 2;
int m1 = median3(a, low, low + eps, low + eps + eps);
int m2 = median3(a, mid - eps, mid, mid + eps);
int m3 = median3(a, high - eps - eps, high - eps, high);
int ninther = median3(a, m1, m2, m3);
exchange(a, low, ninther);
}
// 预处理中已经把轴点放在low位置上
int i = low, j = high + 1;
int p = low, q = high + 1;
Comparable v = a[low];
while (true) {
// 普通快排,但需要特别处理相等的元素来减少重复比较
/*
* 内部排序的处理过程:
* 找到a[i]>v,a[j]<v情况
* 判断边界点(i==j,i>=j)(注意与轴点相等的情况)
* 先处理i,j元素,然后将相等的元素放在区间中(更新p,q)
* 将轴点和其相等放在相应的位置
* 将剩余的不相等的数组,分别排序,重复以上步骤,一直到有序
* */
// a[i]<v
while (less(a[++i], v))
if (i == high) break;
// a[j]>v
while (less(v, a[--j]))
if (j == low) break;
// 边界:i,j指向同一个值,a[i]是否在正确的位置?
if (i == j && eq(v, a[i]))
exchange(a, ++p, i);
// 边界:排序完成
if (i >= j) break;
// 交换之前 a[i]>v,a[j]<v
exchange(a, i, j);
// 更新值相等的区间:更新p,q
if (eq(v, a[i])) exchange(a, i, ++p);
if (eq(v, a[j])) exchange(a, j, --q);
}
i = j + 1;
for (int k = low; k <= p; k++) {
exchange(a, k, j--);
}
for (int k = high; k >= q; k--) {
exchange(a, k, i++);
}
QuickX(a, low, j);
QuickX(a, i, high);
}
// 三分点代码
private static int median3(Comparable[] a, int i, int j, int k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[i], a[k]) ? i : k));
}

Dual-pivot quicksort (JAVA 7 使用)

双轴排序介绍

Dual-pivot quicksort

主要排序算法

mainLoop

最后阶段

finalize

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static void DualPivot(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
// 两个边界点分别为轴,保证轴点有序
if (less(a[hi], a[lo])) exchange(a, lo, hi);
int lt = lo + 1, gt = hi - 1;
int i = lo + 1;
while (i <= gt) {
if (less(a[i], a[lo])) exchange(a, i++, lt++);
else if (less(a[hi], a[i])) exchange(a, i, gt--);
else i++;
}
// 轴点放在合适的位置
exchange(a, lo, --lt);
exchange(a, hi, ++gt);
DualPivot(a, lo, lt);
// (中间数组)当两个轴点不相等时,需要排序
if (less(a[lt], a[gt])) DualPivot(a, lt + 1, gt - 1);
DualPivot(a, hi, gt);
}

优化快排和双轴快排比较(10000随机数字)

QuickX 和 DualPivot比较

参考链接
algs4 uickSort