-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSortRecursion.java
77 lines (69 loc) · 2.07 KB
/
QuickSortRecursion.java
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
package com.blankspace.sort;
public class QuickSortRecursion implements SortInterface {
private volatile static SortInterface sortInstance;
private QuickSortRecursion() {
}
public static SortInterface getInstance() {
if (sortInstance == null) {
synchronized (QuickSortRecursion.class) {
if (sortInstance == null) {
sortInstance = new QuickSortRecursion();
}
}
}
return sortInstance;
}
@Override
public int[] sort(int[] records) {
int length = records.length;
quickSort(records, 0, length - 1);
return records;
}
private void quickSort(int[] records, int first, int end) {
if (first < end) {
// 一次划分
int pivot = partition(records, first, end);
// 对左侧子序列快速排序
quickSort(records, first, pivot - 1);
// 对右侧子序列快速排序
quickSort(records, pivot + 1, end);
}
}
/**
* 一次划分算法
*
* @param first 区间左下标
* @param last 区间右下标
* @return 中轴
*/
private int partition(int[] records, int first, int last) {
// 初始化一次划分区间
int i = first, j = last, temp;
while (i < j) {
// 右侧扫描
while (i < j && records[i] <= records[j]) {
j--;
}
// 将较小记录交换到前面
if (i < j) {
temp = records[i];
records[i] = records[j];
records[j] = temp;
i++;
}
// 左侧扫描
while (i < j && records[i] <= records[j]) {
i++;
}
// 将较大记录交换到后面
if (i < j) {
temp = records[i];
records[i] = records[j];
records[j] = temp;
j--;
}
}
// i为轴值记录的最终位置
return i;
}
}