-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathQuickSort.java
More file actions
58 lines (49 loc) · 1.13 KB
/
QuickSort.java
File metadata and controls
58 lines (49 loc) · 1.13 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
package sort;
import java.util.Arrays;
import java.util.function.IntPredicate;
/*
* 快速排序：
* 选择一个基点，左边都比他小，右边都比他大
* 对基点的左边、右边重复这样操作
*
* */
public class QuickSort extends Sort {
public QuickSort(int[] array) {
super(array);
// TODO Auto-generated constructor stub
}
@Override
public int[] sortAlgorithm(int[] array) {
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));;
return array;
}
public void quickSort(int[] array, int low, int high) {
if(low>=high){
return ;
}
// 用低位作为基准
int index = array[low];
int i=low;
int j=high;
//交替遍历
while (i<j) {
//必须加上:::出现i=j=0的情况出现下标为-1的异常
while(array[j]>=index&&i<j){
j--;
}
if (array[j] < index) {
array[i]=array[j];
}
//必须加上:::出现i=j=length-1时，++的话出现数组越界异常
while(array[i]<=index&&i<j)
i++;
if(array[i]>index){
array[j]=array[i];
}
}
array[i]=index;
quickSort(array,low,i-1);
quickSort(array, i+1, high);
}
}