-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
101 lines (93 loc) · 2.87 KB
/
Copy pathQuickSort.java
File metadata and controls
101 lines (93 loc) · 2.87 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
package sort;
/**
* 快速排序
* 1.从数列中挑出一个元素，称为"基准"（pivot），
* 2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
* 3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* Created by hxchen on 2018/7/9.
*/
public class QuickSort {
/**
* @param arr
* @param head
* @param tail
*/
public static void qSort(int[] arr, int head, int tail) {
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
System.out.printf("head = %d, tail = %d.\t", head, tail);
int i = head, j = tail, pivot = arr[(head + tail) / 2];
System.out.printf("pivot_index = %d,pivot = %d.\t", (head + tail) / 2, pivot);
printArray(arr);
while (i <= j) {
while (arr[i] < pivot) {
++i;
}
while (arr[j] > pivot) {
--j;
}
if (i < j) {
swap(arr, i, j);
++i;
--j;
} else if (i == j) {
++i;
}
}
qSort(arr, head, j);
qSort(arr, i, tail);
}
/**
* 基准为第一个的快速排序
*
* @param arr
* @param start
* @param end
*/
public static void quickSort(int[] arr, int start, int end) {
if (start >= end || arr == null || arr.length <= 1) {
return;
}
// 基准为第一个
int i = start, j = end, pivot = arr[start];
while (i < j) {
// 右边选择第一个比基准小的
while (i < j && arr[j] >= pivot) {
j--;
}
// 左边选择第一个比基准大的
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
swap(arr, start, i);
quickSort(arr, start, i - 1);
quickSort(arr, i + 1, end);
}
public static void main(String[] args) {
int[] arr = new int[]{3, 7, 8, 5, 2, 1, 9, 5, 4};
// qSort(arr, 0, arr.length - 1);
quickSort(arr, 0, arr.length - 1);
String out = "";
for (int digit : arr) {
out += (digit + ",");
}
System.out.println(out);
}
private static void printArray(int[] arr) {
String out = "";
for (int digit : arr) {
out += (digit + ",");
}
System.out.println(out);
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}