算法系列笔记（五）归并排序

归并排序

归并排序的想法就是将一个数组分成两个小数组，每个小数组分别排好序。然后将其按顺序合并到一个新的数组中，这个数组就是所求的数组

    private static void merge(int []a,int low,int mid,int high) {
        int i=low;
        int j=mid+1;
        for(int k=low;k<=high;k++) {
            b[k]=a[k];
        }
        for(int k=low;k<=high;k++) {
            if(i>mid) a[k]=b[j++];
            else if(j>high)a[k]=b[i++];
            else if(b[i]<b[j]) a[k]=b[i++];
            else a[k]=b[j++];
        }
    }

注意这里的b[low]-b[mid]和b[mid+1]-b[high]，b数组是a数组的复制数组，而这两个其实这个是看作成两个数组了。这两个数组一定是要排序（升序）好了。其实很有趣，所谓的合并就是就是比较这两个数组，打擂台。相对较小的元素，则赋值到a数组当中。

但是如何保证b[low]-b[mid]和b[mid+1]-b[high]都是排序好呢？一种方式是用之前的排序方式将b[low]-b[mid]和b[mid+1]-b[high]分别排序。第二种方式使用迭代分解的方式进行归并排序。

public class Mergesort {
    private static int []b;
    public static void sort(int []a) {
        b=new int[a.length];
        sort(a,0,a.length-1);         //high是a.length-1
    }
    private static void sort(int []a,int low,int high) {
        if(high<=low)return;
        int mid=low+(high-low)/2;
        sort(a, low, mid);
        sort(a, mid+1, high);
        merge(a, low, mid, high);
    }
    private static void merge(int []a,int low,int mid,int high) {
        int i=low;
        int j=mid+1;
        for(int k=low;k<=high;k++) {
            b[k]=a[k];
        }
        for(int k=low;k<=high;k++) {
            if(i>mid) a[k]=b[j++];   //其中一方没有元素了，另一方’不战而胜‘
            else if(j>high)a[k]=b[i++];
            else if(b[i]<b[j]) a[k]=b[i++];       //比谁小，‘胜者为王’
            else a[k]=b[j++];
        }
    }
}

这时候需要借助灵魂画手来分析sort是如何工作的。

sort迭代分析图.png

由图可见，迭代的过程中是对数组元素不断地二分，最后将会拆成一个个元素。然后开始回溯Merge，从合并（排序）两个元素开始，慢慢合并的两个数组的元素数越来越多，最终合并成一个数组。

其实sort还有其他一种方法，上面一种方法我们是对一个数组不断进行拆分，这种其实是一种自顶向下的一种看问题的方法。其实我们可以从底向上，直接就从底部看起，直接就合并数组，说实话这个循环很妙，我都想不到

    private static void sort2(int []a) {
        int n=a.length;
        b=new int [n];
        for(int size=1;size<n;size*=2) {
            for(int low=0;low<n-size;low+=(size*2))
                merge(a, low, low+size-1, Math.min(low+size*2-1, n-1));
        }
    }

这里的size从1开始，遍历原数组，让原数组分成一组组小数组，一组数组由两个长度为1的数组组成，然后进行合并排序操作。然后size逐渐变大，然后合并排序的数组就越来越大了，合并的时候始终保证的合并双方的数组都是排序的

归并排序好像速度和希尔排序差不了多少。