将一个数组的最后一位数字(a[q])作为"元",从头a[p]开始跟这个数字比较(索引从i(i=p)开始),使用一个变量作为指针(point) , 如果a[i] 小于 a[q] ,将其与a[point] 互换; 同时 point 向前移动(point++),这样使得比"元"小的数值都放到了a[p] ~ a[point] 之中; 最后将 a[point+1] 与a[q]互换,最后的结果就是以a[point+1] 为界, 左边全小于"元",右边全大于"元";最后左右两边递归调用以上方法即可完成原址排序
public class QuickSortTest {
@Test
public void quickSort_test() {
int[] a = {1,9,3,4,7,2,9,10,14,16};
quickSort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
System.out.print(",");
}
}
private void quickSort(int[] a, int p, int q) {
if(p<q){
int r = partition(a, p, q);
quickSort(a,p,r-1);
quickSort(a,r+1,q);
}
}
private int partition(int[] a, int p, int q) {
int x = a[q];
int point = p-1;
for (int i = p; i < q; i++) {
if(a[i] < x){
point ++;
int temp = a[i];
a[i] = a[point];
a[point] = temp;
}
}
int temp = a[point+1];
a[point + 1 ] = a[q];
a[q] = temp;
return point +1;
}
}
递归调用,复杂度记为O(lgn) ,每次partition 为O(n), 整体复杂度为 O(nlgn) 当然,这个值并不准确,在极端坏的情况下为O(n^2) ,极端好的情况下为O(lgn)