快速的排序逻辑
快速排序的主要思想是递归
Java代码实现
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
|
public class QuickSort {
public static void sort(Comparable[] a) {
Shuffle.shuffle(a);
sort(a, 0, a.length - 1);
}
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);
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
while (true) {
while (less(a[++i], a[lo])) {
if (i == hi) {
break;
}
}
while (less(a[lo], a[--j])) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
swap(a, i, j);
}
swap(a, lo, j);
return j;
}
}
|
小优化
在数组大小较小时,使用插入排序比快速排序执行效率要高。
1
|
private static final int INSERTIONSORT_THRESHOLD = 7;
|
1
2
3
|
if ((hi - lo) < INSERTIONSORT_THRESHOLD) {
InsertionSort.sort(a, lo, hi);
}
|
以上,快速排序的思想真的有些烧脑,实现起来坑还是很多,需要仔细仔细再仔细的思考每一个细节。