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
| /**
* User: fever
* Date: 18-1-9
* Time: 下午1:55
*/
public class MyQuickSort {
private int arr[] = {112, 2, 7, 9, 20, 3, 48, 6, 57, 88, 60, 42, 83, 73, 85};
/**
* 相当于把比基准值小的放在左边，大的放在右边
* 需要重复多次直到左右两边只有一个数，也就是只有三个数，这样一定是有序的
*
* @param arr
* @param lo
* @param hi
* @return
*/
private int partition(int[] arr, int lo, int hi) {
//基准值的索引
int keyIndex = lo;
while (lo < hi) {
//从右向左
while (arr[keyIndex] < arr[hi] && lo < hi) {
hi--;
}
// 基准值和hi值互换
// 基准值索引变为hi
int tmp = arr[hi];
arr[hi] = arr[keyIndex];
arr[keyIndex] = tmp;
keyIndex = hi;
//从左向右
while (arr[keyIndex] > arr[lo] && lo < hi) {
lo++;
}
//基准值和lo值互换
//基准值索引变为lo
tmp = arr[lo];
arr[lo] = arr[keyIndex];
arr[keyIndex] = tmp;
keyIndex = lo;
}
return hi;
}
/**
* 继续分区排序
* 左右两部分递归调用分区函数
*
* @param arr
* @param lo
* @param hi
*/
private void sort(int[] arr, int lo, int hi) {
if (lo >= hi) {
return;
}
// 上次分区的位置
int par = partition(arr, lo, hi);
// 左边排序 递归。。。直到lo>=hi
sort(arr, lo, par - 1);
// 右边排序 递归。。。
sort(arr, par + 1, hi);
}
@org.junit.Test
public void test() {
sort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
|
