-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathCode_04_QuickSort.java
More file actions
162 lines (146 loc) · 5.37 KB
/
Code_04_QuickSort.java
File metadata and controls
162 lines (146 loc) · 5.37 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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
package algorithm.basic;
import java.util.Arrays;
/**
* @Created by mood321
* @Date 2019/10/5 0005
* @Description 荷兰国旗问题来改进快速排序
*/
public class Code_04_QuickSort {
public static void quickSort(int[] arr) {
if(arr==null || arr.length<2){
return;
}
// 快排的思路 拿一个 出来 小的放左边 大的放右边 然后一直拆 拆到大小为1 O(N*Log2(N))
// 不稳定
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int l, int r) {
if(l>=r){
return;
}
// 范围应该在-1 和r+1 但要留一个位置 给选的数
swap(arr, l + (int) (Math.random() * (r - l + 1)), r); // 在L 和R 范围选随机数
int[] p = partition(arr, l, r); // 递归 分治
quickSort(arr,l,p[0]-1);
quickSort(arr,p[1]+1,r);
}
private static int[] partition(int[] arr, int l, int r) {
int less=l-1,more=r;
int num = arr[r]; // num 是随机选出来的
while (l<more){
if (arr[l]<num){
swap(arr,l++,++less);// 把小于的值放到 属于小于范围来
}else if(arr[l]>num){
swap(arr,l,--more);// 同理 但l不变
}else {
l++;
}
}
swap(arr,r,more);
return new int[]{less+1,more};
}
/* public static void quickSort(int[] arr, int l, int r) {
if(l<r){ //只有数组 有多个元素才排序 这也是递归结束条件
// 在普通快速排序中 排序时间复杂度 受数据状况有关 如果最后一个数据项正好是整个数组的等于区域的数 是O(N*log(N))
// 改进 不固定用最后一个 书籍用一个数放在最后 去拍
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r); // 递归 分治
quickSort(arr,l,p[0]-1);// 小于区域 在排序
quickSort(arr,p[1]+1,r);// 大于
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1, more = r;//less 和花旗国问题一致 more 向前一个 用最后一个作为num 划分区域
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, l++, ++less); // 小于的时候 小于区域范围+1（++less） 把当前l 的值和（++less）的值交换 这里（++less）的值要要么是l 要么是等于范围的值 所以交换不会出错
}else if(arr[l]>arr[r]){
swap(arr,l,--more); // 和 小于逻辑一样 但交换玩l不++ 因为小于的交换回来的数要么是小于的（没找到等于的） 要么是等于（找到等于的） 而大于的交换回来的就不一定了
}else {
l++;
}
}
swap(arr,more,r);// r位置必定是 等于r的 交换到等于区域
return new int[]{less+1,more}; // 返回等于区域的下标
}*/
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 comparator(int[] arr) {
Arrays.sort(arr);
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
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 testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
quickSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
quickSort(arr);
printArray(arr);
}
}