快速排序

快速排序

1.快速排序

    /**
     * 快速排序
     * 概述: 将数组按照一个分切元素v(数组中一个值)进行分切,
     * 分切后为: 不大于v的序列(左序列),v,不小于v的序列(右序列)
     * 继续按照上述步骤,分别将左,右序列进行分切,直到无法分切时结束
     * 此时排序完成
     */
    public void quick(int[] arr,int lo,int hi){
        if(lo >= hi) return;
        int j = partition(arr,lo,hi);//分切
        quick(arr,lo,j-1);
        quick(arr,j+1,hi);
    }

    /**
     * 分切方法
     * 将数组arr的[lo...hi]部分按照v = arr[lo]进行分切,分切后其索引为j
     * 分切后, arr[lo...j-1] <= arr[j] <= arr[j+i...hi], 此时arr[j] = v;
     * @param arr 数组
     * @param lo 起始索引
     * @param hi 结束索引
     * @return 返回分切元素的索引
     */
    public int partition(int[] arr,int lo,int hi){
        int v = arr[lo]; //分切元素
        int i = lo, j = hi+1;
        while(true){
            while(v < arr[--j]);
            while(arr[++i] < v) if(i == j) break;
            if(i >= j) break;
            //交换
            exch(arr,i,j);
        }
        exch(arr,lo,j);
        return j;
    }

2.快速排序简单优化

    /**
     * 快速排序简单优化
     * 1.数组规模小于10时使用插入排序
     * 2.每次进行分切时,取首,尾与中间元素的中位数作为分切元素
     *   (此时若将最大元素与尾元素交换则可以去除分切时边界判断)
     *
     * 3.数组规模大时,还可以采用取3组(每组3个数),取每组的中位数(共3个),
     *   然后取这3个中位数的中位数作为分切元素(详见快速三向切分代码)
     */
    public void quickMedian(int[] arr,int lo,int hi){
        int len = hi-lo+1;
        if(len <= 10){ //1. 数组规模小于10时使用插入排序
            insertion(arr,lo,hi);
            return;
        }
        int j = partitionMedian(arr,lo,hi);
        quickMedian(arr,lo,j-1);
        quickMedian(arr,j+1,hi);
    }

    /**
     * 分切方法
     */
    public int partitionMedian(int[] arr,int lo,int hi){
        int len = hi-lo+1;
        setMedian(arr,lo,hi); //2. 从lo,hi,中间处mid三个数中找出中位数与lo交换,最大数与hi交换
        int v = arr[lo]; //分切元素
        int i = lo, j = hi+1;
        while(true){
            while(v < arr[--j]);
            while(arr[++i] < v); // if(i == j) break; 取中位数时,每次最大数与hi交换,因此不需要进行边界判断
            if(i >= j) break;
            //交换
            exch(arr,i,j);
        }
        exch(arr,lo,j);
        return j;
    }

    /**
     * 设置中位数
     * 取首,尾(lo,hi)与中间元素(mid)的中位数作为分切元素(与lo交换)
     * 同时将最大元素与尾(hi)交换(可以去掉分切时边界判断)
     */
    public void setMedian(int[] arr,int lo,int hi){
        int mid = (lo+hi)/2;
        int max = lo;
        if(arr[max] < arr[mid]) max = mid;
        if(arr[max] < arr[hi]) max = hi;
        exch(arr,max,hi);
        if(arr[lo] < arr[mid]) exch(arr,lo,mid);
    }

• 交换方法

    /**
     * 交换方法
     * 交换arr[i] 与 arr[j]
     */
    public void exch(int[] arr,int i,int j){
        if(i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

• 插入排序

    /**
     * 插入排序
     *对序列[lo...hi]部分进行插入排序
     */
    public void insertion(int[] arr,int lo,int hi){
        for(int i=lo+1;i<=hi;++i)
            for(int j=i;j>lo && arr[j]<arr[j-1];--j)
                exch(arr,j,j-1);
    }

3.快速排序—三向切分

    /**
     * 三向切分--针对有较多重复元素的序列进行排序
     * 将序列按照分切元素v切分为: 序列A(小于v) 序列B(等于v) 序列C(大于v)
     * 以此类推,再分别将序列A,序列C切分,直到不可切分时排序完成
     * 特点: 额外交换用于与分切元素不等的元素
     */
    public void quick3Way(int[] arr,int lo,int hi){
        if(lo >= hi) return;
        int v = arr[lo];
        int lt = lo, gt = hi;
        //额外交换用于于分切元素不等的元素
        for(int i=lo+1;i<=gt;++i){//按照[lo...lt-1] < v = arr[lt...gt] < [gt+1...hi]切分
            if (arr[i] < v) exch(arr, lt++, i);
            if (arr[i] > v) exch(arr, gt--, i--);
        }
        //递归
        quick3Way(arr,lo,lt-1);
        quick3Way(arr,gt+1,hi);
    }

4.快速三向切分(熵最优)

    /**
     * 快速三向切分(熵最优)
     * 特点: 额外的交换用于与分切元素v相等的元素
     */
    public void quick3WayPartition(int[] arr,int lo,int hi){
        int len = hi-lo+1;
        if(len <= 10){  //数组规模小于等于10时使用插入排序
            insertion(arr,lo,hi);
            return;
        }
        else if(len <= 40){ //数组规模为(10,40]时取首(lo),尾(hi)与中间元素(mid)的中位数作为分切元素
            int mid = (lo+hi)/2;
            int med = median(arr,lo,mid,hi);
            exch(arr,lo,med);
        }
        else{//数组规模大于40时,分别取三组(每组3个)的中位数,然后再取3个中位数的中位数作为分切元素
            int sep = len / 8;
            int mid = lo + len / 2;
            int m1 = median(arr,lo,lo+sep,lo+sep*2);
            int m2 = median(arr,mid-sep,mid,mid+sep);
            int m3 = median(arr,hi-sep*2,hi-sep,hi);
            mid = median(arr,m1,m2,m3);
            exch(arr,lo,mid);
        }
        int v = arr[lo]; //分切元素
        int i,j,p,q;
        i = p = lo; j = q = hi+1;
        while(true){
            while(v < arr[--j]);
            while(arr[++i] < v) if(i == j) break;
            //if(i == j && arr[i] == v) exch(arr,i,++p); (1).判断相等
            if(i == j) exch(arr,i,++p); //此时直接交换,则最终边界处可能为arr[p] <= v
            if(i >= j) break;
            exch(arr,i,j);
            //将等于分切元素v的移动到两端
            if(arr[i] == v) exch(arr,i,++p);
            if(arr[j] == v) exch(arr,j,--q);
        }
        //此时序列 lo--等于v--p--小于v--i/j--大于v--q--等于v--hi
        //此时i==j或i=j+1,i==j时arr[i] < v  arr[i+1] >v
        i = j + 1;
        //将两端等于分切元素v的元素移动到中间
        //for(int k=lo;k<=p;++k) exch(arr,k,j--); (1).判断相等则,k<=p
        for(int k=lo;k<p;++k) exch(arr,k,j--);  //直接交换则k<p,因为arr[p] <= v
        for(int k=hi;k>=q;--k) exch(arr,k,i++);

        //递归
        quick3WayPartition(arr,lo,j);
        quick3WayPartition(arr,i,hi);
    }

    /**
     * 取中位数
     * 找出arr[lo],arr[mid],arr[hi]的中位数并返回其索引
     */
    public int median(int[] arr,int lo,int mid,int hi){
        return arr[lo]<arr[mid]?(arr[lo]<arr[hi]?(arr[mid]<arr[hi]?mid:hi):lo)
                :(arr[lo]>arr[hi]?(arr[mid]<arr[hi]?hi:mid):lo);
    }

5.多线程并行快速排序

public class Quick<E> extends RecursiveAction{
    private E[] elements;
    private Comparator<E> comparator; //比较器
    private int lo;
    private int hi;

    public Quick(E[] elements, Comparator<E> comparator) {
        this.elements = elements;
        this.comparator = comparator;
        this.lo = 0;
        this.hi = elements.length - 1;
    }
    public Quick(E[] elements) {
        this.elements = elements;
        this.comparator = (E x,E y) -> {
            if(x instanceof Comparable) return ((Comparable) x).compareTo(y);
            else throw new RuntimeException("需要传入Comparator或者实现Comparable");
        };
        this.lo = 0;
        this.hi = elements.length - 1;
    }
    private Quick(E[] elements,int lo,int hi){
        this.elements = elements;
        this.lo = lo;
        this.hi = hi;
    }

    //快排:单线程
    public void sort(){ quickMedian(elements,lo,hi); }
    //快排:多线程并行
    public void parallelSort(){
        ForkJoinPool forkJoin = (ForkJoinPool) Executors.newWorkStealingPool();
        try {
            forkJoin.submit(this).get();//提交任务并获取等待结束
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
        forkJoin.shutdown();
    }

    @Override
    protected void compute() {
        if(hi - lo <= 10000) quickMedian(elements,lo,hi);
        else{
            //分切
            int j = partitionMedian(elements,lo,hi);
            //剩余两部分作为两个分支任务放入ForkJoinPool
            Quick<E> left = new Quick<>(elements,lo,j-1);
            Quick<E> right = new Quick<>(elements,j+1,hi);
            invokeAll(left,right);
        }
    }

    //快速排序: 对[lo,hi]部分进行快速排序
    private void quickMedian(E[] arr,int lo,int hi){
        int len = hi-lo+1;
        if(len <= 10){ //1. 数组规模小于10时使用插入排序
            insertion(arr,lo,hi);
            return;
        }
        int j = partitionMedian(arr,lo,hi);
        quickMedian(arr,lo,j-1);
        quickMedian(arr,j+1,hi);
    }
    private int partitionMedian(E[] arr,int lo,int hi){
        int len = hi-lo+1;
        setMedian(arr,lo,hi); //2. 从lo,hi,中间处mid三个数中找出中位数与lo交换,最大数与hi交换
        E v = arr[lo]; //分切元素
        int i = lo, j = hi+1;
        while(true){
            while(((Comparable)v).compareTo(arr[--j]) < 0);
            while(((Comparable)arr[++i]).compareTo(v) < 0); // if(i == j) break; 取中位数时,每次最大数与hi交换,因此不需要进行边界判断
            if(i >= j) break;
            //交换
            exch(arr,i,j);
        }
        exch(arr,lo,j);
        return j;
    }
    private void setMedian(E[] arr,int lo,int hi){
        int mid = (lo+hi)/2;
        int max = lo;
        if(((Comparable)arr[max]).compareTo(arr[mid]) < 0) max = mid;
        if(((Comparable)arr[max]).compareTo(arr[hi]) < 0) max = hi;
        exch(arr,max,hi);
        if(((Comparable)arr[lo]).compareTo(arr[mid]) < 0) exch(arr,lo,mid);
    }
    private void exch(E[] arr,int i,int j){
        if(i == j) return;
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private void insertion(E[] arr,int lo,int hi){
        for(int i=lo+1;i<=hi;++i)
            for(int j=i;j>lo && ((Comparable)arr[j]).compareTo(arr[j-1]) < 0;--j)
                exch(arr,j,j-1);
    }
}