算法练习(22) - 快排:原址排序

1. 思路

将一个数组的最后一位数字(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] 为界, 左边全小于"元",右边全大于"元";最后左右两边递归调用以上方法即可完成原址排序

2. code

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;
    }

}

3. 复杂度分析

递归调用,复杂度记为$O(lgn)$ ,每次partition 为$O(n)$ , 整体复杂度为 $O(nlgn)$
当然,这个值并不准确,在极端坏的情况下为$O(n^2)$ ,极端好的情况下为$O(lgn)$