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
| /**
* ClassName: QuickSort <br/>
* Description: 快速排序<br/>
* date: 2020-09-29 21:33<br/>
*
* @author hxr<br />
*/
public class QuickSort {
public static void main(String[] args) {
int[] old = {7, 4, 1, 8, 5, 9, 7, 6};
int[] ints = quickSort3(old);
}
//7,4,1,8,5,9,7,6
// 一：一趟遍历数组排序
// 1.找一个基准数，把他拿出来standrad=old[0], old[0]是坑位。
// 2.从右向左找到比基准数小的放在坑位，坑位变成了右边比基准数大的位置
// 3.从左向右找到比基准数大的放在坑位。坑位变成了左边比基准数小的位置
// 4.重复2,3.
// 5.排序成功时i==j退出遍历
// 二：递归分治，
//0,1,2,3,4,5,6,7 数组下标
//sep1
//7,4,1,8,5,9,7,6 //坑位为old[0]
//sep2
//6,4,1,8,5,9,7,6 //sep2,坑位为old[7]
//sep3
//6,4,1,8,5,9,7,8 //sep3,坑位为old[3]
// sep4:
//6,4,1,5,5,9,7,8 //sep2,坑位为old[4]
// sep5: i==j
//6,4,1,5,7,9,7,8 //old[4] = standrad;
// 一：一趟遍历数组排序
// 1.找一个基准数，把他拿出来standrad=old[0], old[0]是坑位。
// 2.从右向左找到比基准数小的放在坑位，坑位变成了右边比基准数大的位置
// 3.从左向右找到比基准数大的放在坑位。坑位变成了左边比基准数小的位置
public static int[] quickSort1(int[] old) {
if (null == old || old.length == 0)
return null;
//sep1
int standrad = old[0];
//sep2
int j = old.length - 1;
for (; j > 0; j--) {
if (old[j] < standrad) {
old[0] = old[j];
break;
}
}
//sep3
int i = 0;
for (; i < old.length - 1; i++) {
if (old[i] > standrad) {
old[j] = old[i];
break;
}
}
return old;
}
// 一：1.找一个基准数，把他拿出来standrad=old[0], old[0]是坑位。
// 2.从右向左找到比基准数小的放在坑位，坑位变成了右边比基准数大的位置
// 3.从左向右找到比基准数大的放在坑位。坑位变成了左边比基准数小的位置
// 4.重复2,3.
// 5.排序成功时i==j退出遍历
public static int[] quickSort2(int[] old) {
int i = 0, j = old.length - 1;
quick(old, i, j);
return old;
}
public static Integer quick(int[] old, int i, int j) {
if (null == old || old.length == 0)
return null;
//sep1 选取基准数old[i],坑位下标为i
int standard = old[i];
//sep4 循环sep2和sep3，直到基准值调整完毕
while (i < j) {
//sep2 从右向左找到比基准值小的下标j，将下标的值old[j]放入旧坑位，下标j变为新坑位。
while (j > i) {
if (old[j] < standard) {
old[i] = old[j];
i++;
System.out.println("旧坑的位置：" + i + ",新坑的位置：" + j);
System.out.println(Arrays.toString(old));
break;
}
j--;
}
//sep3 从左向右找到比基准值大的下标i，将下标的值old[i]放入旧坑位，下标i变为新坑位。
while (i < j) {
if (old[i] > standard) {
old[j] = old[i];
j--;
System.out.println("旧坑的位置：" + j + ",新坑的位置：" + i);
System.out.println(Arrays.toString(old));
break;
}
i++;
}
}
//sep5 退出时i==j，将基准值放入最后的坑位
old[i] = standard;
System.out.print("一趟遍历后的排序结果：");
System.out.println(Arrays.toString(old));
// 返回基准位置的下标
return i;
}
// 一：一趟遍历数组排序
// 二：递归分治
public static int[] quickSort3(int[] old) {
if (null == old || old.length == 0)
return null;
int start = 0, end = old.length - 1;
quick3(old, start, end);
return old;
}
public static void quick3(int[] old, int start, int end) {
// 二、递归分治 退出条件
if (start < end) {
int i = start, j = end;
int standard = old[i];
while (i < j) {
while (j > i) {
if (old[j] < standard) {
old[i] = old[j];
i++;
break;
}
j--;
}
while (i < j) {
if (old[i] > standard) {
old[j] = old[i];
j--;
break;
}
i++;
}
}
old[i] = standard;
System.out.print("一趟遍历后的排序结果：");
System.out.println(Arrays.toString(old));
// 二、递归分治
quick3(old, start, i - 1);
quick3(old, i + 1, end);
}
}
}
|
