我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

经典的十大排序算法！

前言

请==务必==看一下这个：排序算法前置知识+代码环境准备。

当上面的内容都准备好以后，那就开始归并排序吧！

归并排序

1945年由约翰·冯·诺伊曼（John von Neumann）首次提出。

执行流程

• ① 不断地将当前序列平均分割成 2 个子序列
  直到不能再分割（序列中只剩 1 个元素）
• ② 不断地将 2 个子序列合并成一个有序序列
  直到最终只剩下 1 个有序序列

序列分割-divide

sort(0, array.length);
-----------------------------------------------------
/**
 * 对 [begin, end) 范围的数据进行归并排序
 */    
private void sort(int begin, int end){
    if(end - begin < 2) return; // 至少要2个元素
    
    int mid = (begin + end) >> 1;
    sort(begin, mid); // 归并排序左半子序列
    sort(mid, end);    // 归并排序右半子序列
    merge(begin, mid, end); // 合并整个序列
}

序列合并-merge

合并到新序列

将两个序列合并的思路为：左序列和右序列的中元素挨个比较，将较小的放入新序列中，最后新序列中的元素必然升序。

下图中 li，ri 分别代表指向左、右序列的元素索引，ai 为新序列（合并后的序列）的元素索引；
【li】代表左序列 li 位置的元素，【ri】代表右序列 ri 位置的元素，【ai】为新序列 ai 位置的元素；

• 第一轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++;
• 第二轮：【li】 > 【ri】，【ri】放入新数组，【ai】=【ri】，ri++; ai++;
• 第三轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++；
• 第四轮：左序列已经遍历完毕，直接将右序列剩余元素放入新序列，得到新序列（升序）。

原地合并-merge

将两个序列合并时，不一定要合并到新空间，可以合理的利用原空间实现原地合并。

例如：

• 将 array的左半部分[begin, mid)，备份到 leftArray 中；
• 然后将 leftArray 视为==左子序列==，arrary的右半部分[mid, end] 视为==右子序列==；
• 将左子序列和右子序列合并到 array 中。

merge 过程：

• li < ri
  array[ai] = leftArray[li]；
  li++，ai++;
• li >= ri
  array[ai] = array[ri];
  ri++，ai++;

对序列 { 3, 8, 6, 10 } 进行归并排序：

对序列 { 3, 6, 8, 10 } 进行归并排序：左子序列先遍历结束，那就归并结束。

对序列 { 8, 10, 3, 6 } 进行归并排序：右子序列先结束，则将左边剩余全部放入。

原地合并-merge-实现

/**
 * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
 */
private void merge(int begin, int mid, int end){
    int li = 0, le = mid - begin; // 左边数组(基于leftArray)
    int ri = mid, re = end;    // 右边数组(array)
    int ai = begin; // array的索引
    
    // 备份左边数组到leftArray
    for(int i = li; i < le; i++){
        leftArray[i] = array[begin + i];
    }
    
    // 如果左边还没有结束    
    while(li < le){ // li == le 左边结束, 则直接结束归并
        if(ri < re && cmp(array[ri], leftArray[li]) < 0){ // cmp改为<=0会失去稳定性
            array[ai++] = array[ri++]; // 右边<左边, 拷贝右边数组到array
        }else{
            array[ai++] = leftArray[li++]; // 左边<=右边, 拷贝左边数组到array
        }
    }
}

归并排序完整代码

/**
 * 归并排序
 */
@SuppressWarnings("unchecked")
    public class MergeSort <T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;
    
    @Override
    protected void sort() {
        // 准备一段临时的数组空间, 在merge操作中使用
        leftArray = (T[])new Comparable[array.length >> 1];
        sort(0, array.length);
    }
    
    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */    
    private void sort(int begin, int end){
        if(end - begin < 2) return; // 至少要2个元素
        
        int mid = (begin + end) >> 1;
        sort(begin, mid); // 归并排序左半子序列
        sort(mid, end);    // 归并排序右半子序列
        merge(begin, mid, end); // 合并整个序列
    }
    
    /**
     * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
     */
    private void merge(int begin, int mid, int end){
        int li = 0, le = mid - begin; // 左边数组(基于leftArray)
        int ri = mid, re = end;    // 右边数组(array)
        int ai = begin; // array的索引
        
        // 备份左边数组到leftArray
        for(int i = li; i < le; i++){
            leftArray[i] = array[begin + i];
        }
        
        // 如果左边还没有结束
        while(li < le){ // li == le 左边结束, 则直接结束归并
            if(ri < re && cmp(array[ri], leftArray[li]) < 0){ // cmp改为<=0会失去稳定性
                array[ai++] = array[ri++]; // 右边<左边, 拷贝右边数组到array
            }else{
                array[ai++] = leftArray[li++]; // 左边<=右边, 拷贝左边数组到array
            }
        }
    }

}

生成 20000 个取值在[1, 10000] 的随机数进行排序：

复杂度与稳定性

归并排序花费的时间递推式：

• T(n) = 2 ∗ T(n/2) + O(n)
• T(1) = O(1)
• T(n) / n = T(n/2)/(n/2) + O(1)

根据递推式计算复杂度：
令 S~n~ = T(n) / n

• S(1) = O(1)
• S~n~ = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S(n/2^k^) + O(k) = S(1) + O(logn) = O(logn)
• T~n~ = n ∗ S~n~ = O(nlogn)

由于归并排序总是平均分割子列，所以

• 最好、最坏时间复杂度都 O(nlogn)
• 归并排序属于稳定排序
• 归并排序的空间复杂度是 O(n/2 + logn) = O(n)
  n / 2 用于临时存放左侧数组， logn 是因为递归调用

常见的递推式与复杂度

以后遇到复杂的时间复杂度计算，写出递归式直接看这张表即可。

LeetCode真题

88. 合并两个有序数组

题目地址：88. 合并两个有序数组

题目：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。

说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

思路一：从前往后合并

原地合并，nums1 从头往后合并，将 nums2 元素插入到 nums1 时需要将挪动元素，效率较低。

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int li = 0, ri = 0, ai = 0, m2 = m; // 备份一下m        
        while(ri < n){ //nums2遍历完则直接结束
            if(nums1[li] <= nums2[ri] && li < m2){
                li++;
                ai++;
            }else{ // nums1[li] >= nums2[ri]
                // 要令ri指向元素插入到ai, 首先将 ai到ai+li往后移1位
                for(int i = m+n-1; i > ai; i--){
                    nums1[i] = nums1[i - 1];
                }
                nums1[ai++] = nums2[ri++];
                li++;
                m2++;
            }
        }
    }
    
}

思路二：从后往前合并

在思路一的基础上，将从前往后合并变为从后往前合并。

原地合并，nums1 从后往前合并，将 nums2 元素放入 nums1 时无需移动元素，效率较高。

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
         int len = m + n; //从后往前移, 需要合并后的总长度
         for(int i = len - 1; i >=0; i--){
             if(m>0 && n>0 && nums1[m-1] > nums2[n-1]  || n==0){
                 nums1[i] = nums1[--m];
             }else{
                 nums1[i] = nums2[--n];
             }
         }         
     }
     
 }