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
|
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 4, 7, 1, 8, 3, 4};
printArray(arr);
quickSort(arr, 0, arr.length - 1);
printArray(arr);
}
static void quickSort(int[] arr, int i, int j) {
if (i < j) {
int pos = partition(arr, i, j);
printArray(arr);
System.out.println("分别排左边和右边");
quickSort(arr, 0, pos - 1);
quickSort(arr, pos + 1, j);
}
}
static int partition(int[] arr, int i, int j) {
int pivot = arr[j];
System.out.println("基准值：" + pivot);
int cursor = i;
System.out.println("游标：" + cursor);
for (int k = i; k < j; k++) {
System.out.println("循环到第[" + k + "]个值");
if (arr[k] <= pivot) {
System.out.println("交换位置[" + cursor + "]与[" + k + "]的值");
swap(arr, k, cursor);
cursor += 1;
}
System.out.print("循环完成后：");
printArray(arr);
System.out.println("游标：" + cursor);
}
System.out.println("交换位置[" + cursor + "]与[" + j + "]的值");
swap(arr, j, cursor);
System.out.println("游标：" + cursor);
return cursor;
}
static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
static void printArray(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int anArr : arr) {
sb.append(anArr).append(" ");
}
System.out.println(sb.toString().trim());
}
}
|