算法读书笔记-排序算法-快速排序

总结：快速排序大体上也是用的归并的思想，与归并排序不同的是它通过切分确定某一个元素的最终位置并且将较大的数和较小的数分开了，然后按照这个位置切分，快速排序算法的时间复杂度为O(nlgn),在处理大型数据的时候效率比归并算法要高，而且改进后的三向切分的快速排序处理重复元素较多的数据时，时间复杂度可以接近O(n).

快速排序

主要思想：分治法

/*
     * 快速排序
     * 基本思想：找到元素在乱序序列中的位置
     */
    public static void quickShort(Comparable[] a){
        quickShort(a, 0, a.length-1);
    }
    public static void quickShort(Comparable[] a,int lo,int hi){
        if(lo>=hi) return;//if(lo+5>=hi) Insertion(a);改进如果要排序的数组小于5，就转换成插入排序
        int j = partition(a,lo,hi);//切分数组
        quickShort(a,lo,j-1);//对前半部分排序
        quickShort(a,j+1,hi);//对后半部分排序
    }
    
    private static int partition(Comparable[] a, int lo, int hi) {
        // TODO Auto-generated method stub
        int i = lo,j=hi+1;
        Comparable v = a[lo];
        while(true){
            while(less(a[++i],v)) if(i==hi) break;//从左向右找到第一个比v小的数
            while(less(v,a[--j])) if(j==lo) break;//从右向左找到第一个比v大的数
            if(i>=j) break;
            exch(a, i, j);//将比v大的数和比v小的数交换
        }
        exch(a,lo,j);
        return j;
    }

三向切分的快速排序

改进项：在切分时分成三部分

/*
     * 三向切分的快速排序
     * 基本思想：在切分时分成三部分
     */
    private static void quick3Short(Comparable[] a,int lo,int hi){
        if(hi<=lo) return;
        int lt = lo,i = lo+1,gt = hi;
        Comparable v = a[lo];
        while(i<=gt){
            int cmp = a[i].compareTo(v);
            if(cmp<0) exch(a,lt++,i++);
            if(cmp>0) exch(a,gt--,i);
            else i++;
        }
        quick3Short(a, lo, lt-1);
        quick3Short(a, gt+1, hi);
    }