-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSortIteration.java
86 lines (78 loc) · 2.3 KB
/
QuickSortIteration.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
78
79
80
81
82
83
84
85
86
package com.blankspace.sort;
import java.util.ArrayDeque;
import java.util.Deque;
public class QuickSortIteration implements SortInterface {
private volatile static SortInterface sortInstance;
private QuickSortIteration() {
}
public static SortInterface getInstance() {
if (sortInstance == null) {
synchronized (QuickSortIteration.class) {
if (sortInstance == null) {
sortInstance = new QuickSortIteration();
}
}
}
return sortInstance;
}
@Override
public int[] sort(int[] records) {
if (records == null || records.length == 0) {
return records;
}
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
stack.push(records.length - 1);
while (!stack.isEmpty()) {
int high = stack.pop();
int low = stack.pop();
int pivotIndex = partition(records, low, high);
if (pivotIndex - 1 > low) {
stack.push(low);
stack.push(pivotIndex - 1);
}
if (pivotIndex + 1 < high) {
stack.push(pivotIndex + 1);
stack.push(high);
}
}
return records;
}
/**
* 一次划分算法
*
* @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;
}
}