forked from forging2012/JavaArithmetic
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
124 lines (99 loc) · 3.25 KB
/
QuickSort.java
File metadata and controls
124 lines (99 loc) · 3.25 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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package sort;
import java.util.Stack;
/**
* Created by ozc on 2018/3/17.
*
* @author ozc
* @version 1.0
*/
public class QuickSort {
public static void main(String[] args) {
//int[] arr = {1, 4, 5, 67, 2, 7, 8, 6, 9, 44, 34, 5, 5, 2, 34, 5, 62, 42, 1, 1324, 2346};
int[] arr = {23, 34, 33, 56, 45};
quickSort(arr, 0, arr.length - 1);
System.out.println("Java3y " + arr);
}
/**
* 快速排序
*
* @param arr
* @param L 指向数组第一个元素
* @param R 指向数组最后一个元素
*/
public static void quickSort(int[] arr, int L, int R) {
int i = L;
int j = R;
//支点
int pivot = arr[(L + R) / 2];
//左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > arr[i])
i++;
//寻找直到比支点小的数
while (pivot < arr[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
//“左边”再做排序，直到左边剩下一个数(递归出口)
if (L < j)
quickSort(arr, L, j);
//“右边”再做排序，直到右边剩下一个数(递归出口)
if (i < R)
quickSort(arr, i, R);
}
//-----------------Stack方式实现快速排序
public static void print(int[] arr) {
for (int n = 0; n < arr.length; n++) {
System.out.print(arr[n] + " ");
}
System.out.println();
}
public static void fun(int[] a, int low, int high) {
Stack<Integer> stack = new Stack<>();
if (low < high) {
stack.add(low);
stack.add(high);
while (!stack.isEmpty()) {
int hi = stack.pop();
int lo = stack.pop();
int key = partition(a, lo, hi);
if (lo < key - 1) {
stack.push(lo);
stack.push(key - 1);
}
if (hi > key) {
stack.push(key + 1);
stack.push(hi);//这样，最后入栈的就是key右边的部分，则下一次循环先处理key右边的部分
}
}
}
}
public static int partition(int[] a, int low, int high) {
// 选第一个元素作为key
int key = a[low];
while (low < high) {
// 右边找到比key还要小的
while (a[high] >= key && low < high) {
high--;
}
a[low] = a[high];
// 左边找到比key要大的
while (a[low] <= key && low < high) {//小于于等于key的数组元素不需要移动
low++;
}
a[high] = a[low];
}
a[low] = key;
print(a);
return low;
}
}