转载

复杂排序之归并、快速、三向切分、堆详细总结

归并排序(MergeSort)

复杂度 O(nlogn) .

核心思想就是采用分而治之的方法，递归的合并两个有序的数组。效率比较高，缺点是空间复杂度高，会用到额外的数组。

原理

核心代码是合并的函数。合并的前提是保证左右两边的数组分别有序，在合并之前和之后在 Java 中我们可以用断言来保证数组有序。

合并的原理其实也很简单，先把 a 数组中的内容复制到额外储存的 temp 数组中去。分别用两个 index 指向 a 数组的起始位置和中间位置，保证 a 数组左右两边有序，比如 i ， j 。现在开始从头扫描比较左右两个数组,若 a[i]<=a[j] ，则把 a[i] 放到 temp 数组中去，且 i 向前走一步。反正则放 a[j] ，且 j 走一步。若其中一个数组走完了，则把另一个数组剩余的数直接放到temp数组中。

我们用递归的方式来实现左右两边有序。递归到数组只有1个数时肯定是有序的，再合并2个数，再退出来合并4个数，以此类推。

复杂排序之归并、快速、三向切分、堆详细总结

实现

public class MergeSort extends BaseSort {
    Comparable[] temp ;
    private void merge(Comparable[] a, int l, int m, int h){

        for(int i=l;i<=h;i++){
            temp[i]=a[i];
        }

        int i=l;
        int j=m+1;

        for(int k=l;k<=h;k++){
            if(i>m) a[k]=temp[j++];
            else if(j>h) a[k]=temp[i++];
            else if(less(temp[i],temp[j])) a[k]=temp[i++];
            else a[k] = temp[j++];
        }

    }

    private void sort(Comparable[] a,int l,int h) {
        if(l<h){
            int mid = (l+h)/2;
            sort(a,l,mid);
            sort(a,mid+1,h);
            merge(a,l,mid,h);
        }
    }

    @Override
    public void sort(Comparable[] a) {
        temp = new Comparable[a.length];

        sort(a,0,a.length-1);
    }

}

优化

归并排序对小数组排序时，由于会有多重的递归调用，所以速度没有插入排序快。可以在递归调用到小数组时改采用插入排序。小数组的意思是差不多10个数左右。

如果递归时判断已经有序则不用继续递归。也可以增加效率。

private void sort(Comparable[] a,int l,int h) {
        if(l<h){
            int mid = (l+h)/2;
            sort(a,l,mid);
            sort(a,mid+1,h);
            if (!less(a[mid+1], a[mid])) return;
            merge(a,l,mid,h);
        }
    }

另外在合并时交互两个数组的顺序，能节省复制数组到辅助数组的时间，但节省不了空间。

适用范围

如果你对空间要求不高，且想要一个稳定的算法。那么可以使用归并排序。

快速排序

传说中最快的排序算法，听说能裸写快排，月薪可上10k（ps.不是我说的。）

快排平均情况下时间复杂度 O(nlogn) ，最糟糕情况 O(n²) 。 O(n²) 主要是因为选定的主元是极端值造成的，比如说最大值，最小值。不过这种情况一般很少出现，所以在进行快排之前我们需要对数组进行乱序，尽量避免这种情况的发生，

原理

第一步打乱数组。

然后也是分治法。归并是先分再合并。快排是先排序再分别排序两边。

排序过程核心思想是为了选出一个数，把数组分成左右两边，左边比主元小，右边比主元大。

选定第一个数作为主元。然后设定两个index指向数组首尾，比如 i ， j 。接着从两边向中间扫描，分别用 a[i] 和 a[j] 和主元比较。若两边位置不对则交换 a[i] 和 a[j] ，比如说 a[i] 在扫描过程中遇到 a[i]>主元 ，那么则停止扫描,因为我们需要左边的数小于主元,反正右边也一样等到 a[j] 也停下来,则交换 a[i] 和 a[j] .

得到中间的位置之后再分别左右递归排序。

复杂排序之归并、快速、三向切分、堆详细总结

优化

第一步的随机打乱数组，虽然会耗费一定时间，但却是必要的。

同样的小数组的排序，快排不如插入排序。所以小数组可以直接采用插入排序。

主元的选择方式可以有多种，比如随机选择主元。或者选取三个数，取中位数为主元，但是会耗费一定时间。

适用范围

虽然快速排序是不稳定的。但快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环很小。

快速排序在对重复数据的排序时，会重复划分数据进行排序。虽然性能也还行，但这里可以进行改进，就是下面介绍的三向切分排序。

三向切分(3-way partitioning)

快速排序的一种改进，使快排在有大量重复元素的数据，同样能保持高效。

原理

基本原理和快排差不多。三向切分的时候在划分数组时不是分为两组，而是分成三组。

小于主元
和主元相等
大于主元

复杂排序之归并、快速、三向切分、堆详细总结

具体排序方式和快排差不多我就不赘述了，我觉得三向切分代码写起来比快排要简单。大家直接看代码吧

实现

public class ThreeWaySort extends BaseSort {
    @Override
    public void sort(Comparable[] a) {
        sort(a,0,a.length-1);
    }
    
    public void sort(Comparable[] a,int l ,int h) {
        if(l>=h) return;
        Comparable v = a[l];
        int i=l;
        int lv=l;
        int gh=h;
        while(i<=gh){
            int cmpIndex = a[i].compareTo(v);
            if(cmpIndex<0) exch(a,i++,lv++);
            else if(cmpIndex>0) exch(a,i,gh--);
            else i++;
        }
        sort(a,l,lv-1);
        sort(a,gh+1,h);
    }
}

堆排序

时间复杂度 O(nlogn) ，堆排序主要用二叉堆实现，在讲堆排序之前我们可以要先了解下二叉堆。

二叉堆

所谓的二叉堆用一颗二叉树表示，也就是每一个节点都大于它的左右子节点。也就是说根节点是最大的。

二叉树用数组存储，可以用下标来表示节点。比如 i 这个节点的父节点为 i/2 ，左儿子为 2*i ，右儿子为 2*i+1 .

堆的操作主要有两种上浮和下沉。主要对应两种情况，比如在数组末尾添加节点，此时需要上浮节点，保证二叉堆的特点。反之在替换根节点是则需要下沉操作。

//上浮
public void swim(int k){
    while(k/2>=1 && less(pq[k/2],pq[k])){
        exch(pq,k/2,k);
        k=k/2;
    }
}
//下沉
private void sink() {
    int k=1;
    while(2*k<N){
        int j=2*k;
        if(less(pq[j],pq[j+1])) j++;
        if(less(pq[k],pq[j])) exch(pq,k,j);
        else break;
        k = j;
    }
}

堆排序实现原理

分为两步。

把数组排成二叉堆的顺序
调换根节点和最后一个节点的位置，然后对根节点进行下沉操作。

复杂排序之归并、快速、三向切分、堆详细总结

实现

可能我的代码和上面的动画略有出入，不过基本原理差不多。

public class HeapSort extends BaseSort {

    private int N;
    @Override
    public void sort(Comparable[] a) {
        N =a.length-1;
        int k = N/2;
        while(k>=1){
            sink(a,k);
            k--;
        }
        k = 1;
        while(k<=N){
            exch(a,k,N--);
            sink(a,k);
        }
    }
}