数据结构--排序之归并排序（分治 递归 合并典型案例）

归并排序的运行时间是O（NlogN）

归并排序是用于分析递归技巧的典型案例

与其他的O（NlogN）排序算法比较 比如堆排序 归并排序的运行时间严重依赖比较时间和数组和临时数组中移动元素的开销，这些开销是和语言相关的。比如进行一次泛型排序，使用Comparactor时。归并排序使用流行算法中最少的比较次数，因此是使用Java的通用排序算法的上好选择。事实上，他就是java标准类库中泛型排序所使用的标准算法。

上代码:

//并归排序  在分治中递归再合并  使用一个与原数组大小一样的空数组来进行合并操作
    //正向调用的时候 t和tmpArray数组都是没有值 而从栈中弹出  开始返回操作的时候开始两个数组往里面一点点的增加东西
    private static <T extends Comparable<? super T>> void mergeSort(T[] t,T[] tmpArray,int left,int right)
    {
        //如果只剩一个元素的情况 也就是left==right 此时不操作  直接返回  待上级直接进行合并操作
        if(left<right)
        {
            int center=(left+right)/2;
            mergeSort(t,tmpArray,left,center);
            mergeSort(t,tmpArray,center+1,right);
            //经过上面两个式子的运算以后  t数组的左右两个部分已经被改变 其实 tmpArray数组也是被改变了  不过这不重要  因为不仅是tmpArray还有t数组都要继续被改写
            merge(t,tmpArray,left,center+1,right);
        }

    }
    //进行合并操作
    private static <T extends Comparable<? super T>> void merge(T[] t,T[] tmpArray,int leftPos,int rightPos,int rigthEnd)
    {
        int tmpPos=leftPos;
        int leftEnd=rightPos-1;
        int numElements=rigthEnd-leftPos+1;//看此次合并了多少个元素  便于把tmpArray中的元素拷贝到 t数组中去
        //只要两部分中 有一部分已经全部比较完（此处是都太小了） 计数的指针已经跑出来>右边界  那么就停止比较 直接执行下一步  把剩余的那一个也就是left<right的一半全部拷贝到tmpArray中去
        while(leftPos<=leftEnd && rightPos<=rigthEnd)
        {
            if(t[leftPos].compareTo(t[rightPos])<=0)
                tmpArray[tmpPos++]=t[leftPos++];
            else
                tmpArray[tmpPos++]=t[rightPos++];
        }
        //把剩余部分全部加入tmpArray 如果是左边没有加完
        while(leftPos<=leftEnd)
            tmpArray[tmpPos++]=t[leftPos++];
        //如果是右边没有加完
        while(rightPos<=rigthEnd)
            tmpArray[tmpPos++]=t[rightPos++];
        //此时tmpArray已经把leftPos到rigthEnd部分的元素全部排序正确比如说是0-3部分  我们需要把这部分的值全部更新到t数组中  为下一步（0-7）提供左边部分的值
        //执行numElements次  也就是numElements个元素
        for(int i=0;i<numElements;i++,rigthEnd--)
            t[rigthEnd]=tmpArray[rigthEnd];
    }
    //对归并排序进行驱动的程序
    public static <T extends Comparable<? super T>> void mergeSort(T[] t)
    {
        //注意泛型数组不能直接new 需要用到强制转换
        T[] tmpArray=(T[])new Comparable[t.length];
        mergeSort(t,tmpArray,0,t.length-1);
    }