快速排序-维基百科

一次快排分区的结果

快排

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
class QuickSort {

private int[] mArray;

public QuickSort(int[] array) {
this.mArray = array;
}

private void swap(int from, int to) {
int t = mArray[from];
mArray[from] = mArray[to];
mArray[to] = t;
}

/**
* 分区(原地版本)
*
* @param left 数组左侧
* @param right 数组末尾
* @return 分区下标
*/
private int partition(int left, int right) {
//选择左则作为分区基准值
int pivotValue = mArray[left];
//将基准移到尾部
swap(left, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (mArray[i] <= pivotValue) {
swap(storeIndex, i);
storeIndex++;
}
}
//将基准移到分区位置
swap(right, storeIndex);
return storeIndex;
}

/*
* 分区(基础版本)
* 以每次分区left元素为标志
*/
private int partition(int left, int right) {
int key = arr[left];
while (left < right) {
while (left < right && arr[right] >= key) {
right--;
}
if (left < right)
arr[left] = arr[right];
while (left < right && arr[left] < key) {
left++;
}
if (left < right)
arr[right] = arr[left];
}
arr[left] = key;
return left;
}

public void sort(int left, int right) {
if (right > left) {
//进行分区,返回分区下标
int pivotNewIndex = partition(left, right);
sort(left, pivotNewIndex - 1);
sort(pivotNewIndex + 1, right);
}
}
}