-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquicklySort.java
More file actions
107 lines (95 loc) · 2.36 KB
/
quicklySort.java
File metadata and controls
107 lines (95 loc) · 2.36 KB
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
* @author LZD 2018/03/01
*/
/*
* 随机快速排序
* 时间复杂度：O(N*logN)，额外空间复杂度：O(logN)
* 时间复杂度是由一个长期数学期望计算得出的
* 额外空间复杂度是由记录边界的数组数量计算的，
* 类似于将其一层一层二分出来的树的深度
*/
package class02;
public class quicklySort {
public static void quickSort(int[] arr) {
// 如果为空或长度为1不需要排序，直接返回
if(arr == null || arr.length < 2)
return;
else
quickSort(arr, 0, arr.length - 1);
}
// 递归排序
public static void quickSort(int[] arr, int L, int R) {
if(L < R) {
/*
* 随机快排的随机就在这
* 是随机选取了一个数，和 R 进行了交换，然后使用这个数作为num，
* 所以每次选取的num是随机的，
* 在计算时间复杂度时，是没有最优最差情况的
* 而是通过一个长期的数学期望计算的，结果是O(N*logN)
*/
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] border = partition(arr, L, R);
// 小于区和大于区进行递归
quickSort(arr, L, border[0] - 1);
quickSort(arr, border[1] + 1, R);
}
}
// 将给定数组划分为小于区、等于区和大于区
public static int[] partition(int[] arr, int L, int R) {
int num = arr[R];
int less = L - 1;
int more = R + 1;
int curr = L;
while(curr < more) {
if(arr[curr] < num) {
swap(arr, curr++, ++less);
} else if(arr[curr] > num) {
swap(arr, curr, --more);
} else {
curr++;
}
}
return new int[] {less + 1, more - 1};
}
/*
* 老师写的：
* 取最后一个数作为num，这个方法是将num直接归在>num区中，
* 在划分之后再将最后位置上的与大于区的第一个进行交换，
* 就可以得到左边是小于区，中间是等于区，右边是大于区了
* emmm好处就是可以少一个变量kkk
*/
public static int[] partition2(int[] arr, int L, int R) {
int less = L - 1;
int more = R;
while(L < more) {
if(arr[L] < arr[R]) {
swap(arr, L++, ++less);
} else if(arr[L] > arr[R]) {
swap(arr, L, --more);
} else {
L++;
}
}
swap(arr, more, R);
return new int[] {less + 1, more - 1};
}
// 交换
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// for test 打印数组
public static void printArray(int[] arr) {
for(int i = 0;i < arr.length;i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int[] arr = {2, 1, 3, 6, 0, 5, 3, 4, 7, 0, 1, 2};
quickSort(arr);
printArray(arr);
}
}