【数据结构与算法】归并排序

归并排序的原理

归并排序的思想是如果要排序一个数组，需要把数组分为两部分，然后对两部分分别进行排序，再将排序好的数组合并起来。归并排序其实分为两个步骤，先进行待排数据的分解，再对最小集进行排序，在进行合并。

归并排序其实就是一个分治的思想，分一般采用的形式是递归来解决的，而治在这里指的是把各阶段的答案拼在一起。

image

归并排序的伪代码

第一个方法{
创建一个和原数组一样大的临时数组。
调用第二个方法，参数为0，数组长度-1，原数组，临时数组temp
}

第二个方法
{
递归的出口是数组的长度为1。
对待排序数组进行二分，分为左分区，和右分区。
递归的进行切分下去
对左分区和右分区进行merge操作，合并数组。merge方法传入的参数为：待排序区间的边界索引（三个），原数组，临时数组
}

第三个方法merge{
遍历待排区间，依次比较左区间右区间的数的大小，小的数放到临时区间中，直到某个区间遍历完成
遍历未遍历完的剩余区间的数，依次追加到临时数组。
拷贝临时数组至原数组中。
}

代码示例

public class MergeSort {
    public static void main(String[] args){
        int a[] = {9,8,7,6,5,4,3,2,1,0};
        mergeSort(a);
        System.out.println("ok:" + Arrays.toString(a));
    }

    public static void mergeSort (int[] num){
        if(num==null || num.length==1){
            return;
        }
        int[] temp = new int[num.length];
        sort(num,temp,0,num.length-1);

    }

    public static void sort(int[] num,int[] temp,int left,int right){
        if(left>=right){
            return;
        }
        int mid = (left+right)/2;
        sort(num,temp,left,mid);
        sort(num,temp,mid+1,right);

        merge(num,temp,left,mid,right);
        System.out.println(Arrays.toString(num));
    }

    public static void merge(int[] num,int[] temp,int left,int mid,int right){
        int k =left;
        int l = left;
        int r = mid+1;

        while(l<=mid&&r<=right){
            if(num[l]<num[r]){
                temp[k++]=num[l++];
            }else{
                temp[k++]=num[r++];
            }
            //System.out.println("ssss"+Arrays.toString(temp));
        }
        int start = l;
        int end = mid;
        if(r<right){
            start= r;
            end = right;
        }
        while(start <= end){
            temp[k++] = num[start++];
        }

        for(int i = left;i<=right;i++){
            num[i]=temp[i];
        }
    }

}

性能分析

最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
对于长度为 N 的任意数组，自顶向下的归并排序需要 1/2NlgN - NlgN 次比较。
对于长度为 N 的任意数组，自顶向下的归并排序最多需要访问数组 6NlgN 次（2N 次用来复制、2N 次用来将排好序的元素移动回来、另外最多比较 2N 次）。