快速排序及优化
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
一. 普通快速排序
找一个基准值base，然后一趟排序后让base左边的数都小于base，base右边的数都大于等于base。再分为两个子数组的排序。如此递归下去。
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
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
T base = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (base.compareTo(arr[i]) > 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, left, j);
return j;
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
二. 快速排序优化：随机选取基准值base
在数组几乎有序时，快排性能不好（因为每趟排序后，左右两个子递归规模相差悬殊，大的那部分最后很可能会达到O(n^2)）。
解决：基准值随机地选取，而不是每次都取第一个数。这样就不会受“几乎有序的数组”的干扰了。但是对“几乎乱序的数组”的排序性能可能会稍微下降，至少多了排序前交换的那部分，乱序时这个交换没有意义…有很多“运气”成分..
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
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
swap(arr,left,(int)(Math.random()*(right - left + 1)+left));
T base = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (base.compareTo(arr[i]) > 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, left, j);
return j;
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
三. 快速排序继续优化：配合着使用插入排序
快排是不断减小问题规模来解决子问题的，需要不断递归。但是递归到规模足够小时，如果继续采用这种 不稳定+递归 的方式执行下去，效率不见得会很好。
所以当问题规模较小时，近乎有序时，插入排序表现的很好。Java自带的Arrays.sort()里经常能看到这样的注释：“Use insertion sort on tiny arrays”，“Insertion sort on smallest arrays”
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
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
if (right - left <= k) {
insertionSort(arr, left, right);
return;
}
int p = partition(arr, left, right);
sort(arr, left, p - 1, k);
sort(arr, p + 1, right, k);
}
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
T cur = arr[i];
int j = i - 1;
for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = cur;
}
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (base.compareTo(arr[i]) > 0) {
j++;
swap(arr, j, i);
}
}
swap(arr, left, j);
return j;
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
四. 快速排序继续优化：两路快排
在最开始的普通快速排序说过，让基准值base左边的都比base小，而base右边的都大于等于base。等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候，就又会导致两边子递归规模差距悬殊的情况。这时想把等于base的那些数分派到base两边，而不是让他们聚集到一起。
（注：测试代码的时候，最好把插入排序那部分注视掉，向我下面代码中那样…不然数据量小于k=16的时候执行的是插入排序…..）
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
80
81
82
83
84
85
86
87
88
89
90
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1, k);
sort(arr, p + 1, right, k);
}
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
T cur = arr[i];
int j = i - 1;
for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = cur;
}
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= right && arr[i].compareTo(base) < 0) i++;
while (j >= left && arr[j].compareTo(base) > 0) j--;
if (i > j) {
break;
}
swap(arr, i++, j--);
}
swap(arr, left, j);
return j;
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
五. 快速排序继续优化：两路快排 不用swap, 用直接赋值
上面的两路在找到大于base的值和小于base的值时，用的是swap()方法来进行交换。两数交换涉及到第三个变量temp的操作，多了读写操作。接下来用直接赋值的方法，把小于的放到右边，大于的放到左边，当i和j相遇时，那个位置就是base该放的地方。至此一趟完成。递归即可。
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
80
81
82
83
84
85
86
87
88
89
90
91
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
if (left >= right) return;
int p = partition(arr, left, right);
sort(arr, left, p - 1, k);
sort(arr, p + 1, right, k);
}
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
T cur = arr[i];
int j = i - 1;
for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = cur;
}
}
private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
int i = left;
int j = right;
while (i < j) {
while (j > i && arr[j].compareTo(base) > 0) j--;
arr[i] = arr[j];
while (i < j && arr[i].compareTo(base) < 0) i++;
arr[j] = arr[i];
}
arr[j] = base;
return j;
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
六. 快速排序继续优化：当大量数据，且重复数多时，用三路快排
把数组分为三路，第一路都比base小，第二路都等于base，第三路都大于base。
用指针从前到后扫描，如果：
1.cur指向的数小于base，那么：交换arr[cur]和arr[i]的值，然后i++,cur++。
2.cur指向的数等于base, 那么：cur++
3.cur指向的数大于base，那么：交换arr[cur]和arr[j]的值，然后j—。
当cur > j的时候说明三路都已经完成。
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
if (left >= right) return;
int[] ret = partition(arr, left, right);
sort(arr, left, ret[0], k);
sort(arr, ret[1], right, k);
}
public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
T cur = arr[i];
int j = i - 1;
for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = cur;
}
}
private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
int i = left;
int j = right;
int cur = i;
while (cur <= j) {
if (arr[cur].compareTo(base) == 0) {
cur++;
} else if (arr[cur].compareTo(base) < 0) {
swap(arr, cur++, i++);
} else {
swap(arr, cur, j--);
}
}
return new int[]{i - 1, j + 1};
}
public static void swap(Object[] arr, int i, int j) {
if (i != j) {
Object temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
private static void printArr(Object[] arr) {
for (Object o : arr) {
System.out.print(o);
System.out.print("\t");
}
System.out.println();
}
public static void main(String args[]) {
Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
printArr(arr);
sort(arr);
printArr(arr);
}
}
|
Copyright 2021 sunfy.top ALL Rights Reserved