快排

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
public class QuickSort {
public static void main(String[] args) {
int[] a = {2,7,3,6,9,1};
QuickSort quickSort = new QuickSort();
quickSort.quickSort(a);
for (int i : a) {
System.out.println(i);
}
}

void quickSort(int[] array){
qSort(array,0,array.length-1);
}

void qSort(int[] array, int low, int high){
if (low<high){//长度大于1
int pivotloc = partition(array,low,high);
qSort(array,low,pivotloc-1);
qSort(array,pivotloc+1,high);
}
}

int partition(int[] array, int low, int high){
int pivotkey = array[low];
while (low<high){
while (low<high&&array[high]>=pivotkey)
--high;
array[low] = array[high];
while (low<high&&array[low]<=pivotkey)
++low;
array[high]=array[low];
}
array[low]=pivotkey;
return low;
}
}