导航
导航

快速排序算法

Quick sort algorithm

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
/**
* 快速排序算法 java实现
* @param arr 待排序数组
* @author youqi
*/
public void quickSort(int[] arr) {
if (arr == null || arr.length < 1)
return;
quickSort(arr, 0, arr.length - 1);
}

private void quickSort(int[] arr, int start, int end) {
//记录初始状态
int i = start;
int j = end;

//选择第一个为key
int key = arr[start];

while (start < end) {
//从后向前搜索比key小的数
while (arr[end] >= key && end > start)
end--;

//避免不必要的交换
if (arr[end] < key)
swap(arr, start, end);

//从前往后搜索比key大的数
while (arr[start] <= key && start < end)
start++;

if (arr[start] > key)
swap(arr, start, end);
}

//start > i 说明start以前还存在待排序的元素
if (start > i)
quickSort(arr, i, start - 1);

//end < j 说明end以后还有待排序的元素
if (end < j)
quickSort(arr, end + 1, j);

}

private void swap(int[] arr, int a, int b) {
arr[a] = arr[a] ^ arr[b];
arr[b] = arr[a] ^ arr[b];
arr[a] = arr[a] ^ arr[b];
}