Day22:[排序演算法]Merge sort - 合并排序法

Merge Sort采用分治法(Divide and Conquer)的方式来处理排序的问题，简单介绍一下分治法执行的步骤如下

• Divide:先将大问题不断切割成小问题
• Conquer:用递回的方式处理所有的子问题
• Combine:将所有的结果合并起来就是最终解答

实作步骤

将阵列不断分割，分割到只有一个元素为止，再依照大小依序组合起来，流程可参考下图

用js实作merge sort

const merge = (arr1, arr2) => {
    const result = [];
    //用双指针来纪录比较位置
    let i = 0;
    let j = 0;

    //两个阵列里的元素逐一比较大小
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] > arr2[j]) {
            result.push(arr2[j]);
            j++;
        } else {
            result.push(arr1[i]);
            i++;
        }
    }

    //将剩余的元素放入result
    while (i < arr1.length) {
        result.push(arr1[i]);
        i++;
    }
    while (j < arr2.length) {
        result.push(arr2[j]);
        j++;
    }
    return result;
};

const mergeSort = (arr) => {
    if (arr.length === 1) return arr;
    //找中间点
    let middle = Math.floor(arr.length / 2);
    //将阵列切为左半边和右半边
    let left = arr.slice(0, middle);
    let right = arr.slice(middle, arr.length);
    return merge(mergeSort(right), mergeSort(left));
};

mergeSort([8, 3, 6, 7, 2]);

这边画流程图来讲解merge这个函式在做的事情

1. 假设传入两个阵列个别是arr1 和arr2 (这两个必定是已经排序好的阵列)
   

2. 第一个while回圈会搭配双指针将两个阵列相互比大小，先取两个阵列中的第一个来做比较，1比2小所以放入result里面，然後本来指向1的j指针就要往後移动一格，指向4
   

3. 2与4做比较，2比较小所以放入result中，本来指向2的i指针就要往後移动一格，指向3
   

4. 经过不断的比较会发现i指针已经指到最後一个了，但是j指针还没到终点，此时第一个while回圈已经终止，可以发现arr1的已经全部被放进result里面了，arr2还有两个
   

5. 因此会执行第三个while回圈，将arr2剩下的元素放进result，如果今天是arr1有剩余的元素就会执行第二个while回圈，最後可以得到一个合并好的阵列并且排序由小到大
   

空间复杂度相较其它排序演算法会比较高，因为会不断切割生成新的阵列，需要额外的记忆体空间来存放

时间复杂度

• 在最差的情况下，时间复杂度是O(n log n)
• 在最佳的情况下，时间复杂度是O(n log n)
• 在平均情况下，时间复杂度为 O(n log n)

参考资料: divide-and-conquer