1.归并排序

具体参考前面的章节： (3)分治策略

归并排序是性能比较好的一种排序方法，它的时间复杂度是O(nlgn)，是典型的运用了分治思想的算法。归并排序的步骤如下：

• 分解：将待排序的n个元素分解成n/2的子序列。
• 解决：使用归并排序递归的排列两个子序列。
• 合并：将两个已排序的子序列合并得出结果。

代码如下：

/**
 * @Project:
 * @description:   归并排序
 * @author: sunkang
 * @create: 2018-08-15 20:19
 * @ModificationHistory who      when       What
 **/
public class MergerSort {
    /**
     * 归并排序算法
     *分治方法核心思想为：
     *1.分解： 分解两个子数组
     *2.解决： 递归的解决两个子问题
     *3.合并： 合并两个有序的子问题的集合
     * @param A   将要排序的数组
     * @param low  数组的要排序的地位
     * @param high  数组排序的高位
     */
    public  void mergerSort(int[] A,int low ,int high ){
        if(low < high){
            //1.分解  分解两个子数组
            int mid  = (low+high)/2;
            //2.解决    递归的解决两个子问题
            mergerSort(A,low,mid);
            mergerSort(A,mid+1,high);
            //3合并    合并两个有序的子问题的集合
            merger(A,low,mid ,high);
        }
    }
    /**
     * 进行子数组合并操作
     * @param A   数组A
     * @param low  低位
     * @param mid  中位
     * @param high  高位
     */
    public  void merger(int[] A ,int low ,int mid ,int high){
        //得到子问题1的集合大小和子问题2的集合大小为n1 和n2
        int n1 = mid - low + 1;
        int n2 = high - mid;
        //创建两个临时数组,然后赋值
        int[] L = new int[n1];
        int[] R = new int[n2];
        for(int i =0;i < n1  ;i++){
            L[i]  = A[low + i];
        }
        for(int i = 0; i<n2; i++){
            R[i] = A[mid + 1 + i];
        }
        //进行两个子数组合并
        int i =0;
        int j =0;
        for(int  k = low;k<= high;k++ ){
            if(i == n1){
                A[k]  = R[j++];
            }else if( j  == n2){
                A[k]  = L[i++];
            }else if( L[i] <= R[j]){
                A[k]  = L[i++];
            }else{
                A[k]  = R[j++];
            }
        }
    }
    public void display(int[] arr){
        for(int i :arr){
            System.out.print(i+",");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MergerSort sort  = new MergerSort() ;
        int[]  arr = new int[]{1,2,7,4,3,9};
        sort.mergerSort(arr,0,arr.length-1);
        sort.display(arr);
    }
}

下面分析一下归并排序的时间复杂度。

分解：分布步骤仅仅计算子数组的中间位置，需要常量时间，因此，D(n) = Θ(1);
解决： 递归的求解两个子规模为n/2的子问题，将贡献2T(n/2)的运行时间
合并： 注意一个具有n个 元素的子数组上merge需要 Θ(n)的时间，所以C(n)= Θ(n);

归并排序最坏情况运行时间T(n)的递归式如下：

归并排序递归式.png