归并排序

概念

归并排序(merge sort) 是建立在归并操作上的一种有效的排序算法。

该方法是采用分治法的一种非常典型的应用，将已经有序的序列合并，得到完整的有序的序列。

归并排序.png

步骤：

百科例子 设有数列{6，202，100，301，38，8，1}
将数列分解成单个：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；

---

时间复杂度： 平均时间复杂度为O(n log n) 。

算法稳定性：是一个稳定的排序算法。

算法实现

function mergeSort(arr) {
    // 判断是否是数组，不是则抛出错误
    if(!Array.isArray(arr)) throw new Error('传入的不是数组')

    const len = arr.length;

    // 判断长度是否小于等于1，是则直接返回
    if(len <= 1) return arr;

    //将数据分成左右组，对左右两组接着分组，直到数据长度为1，再进行合并
    const middle = Math.floor(len / 2),
    left = arr.slice(0,middle),
    right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
    let result = [];

    while(left.length > 0 && right.length > 0) {
        // 左边的第一个元素和右边的第一个元素比较，大于的添加进入
        // 小于等于的话将left的第一个之加入
        if(left[0] > right[0]) {
            result.push(right.shift());
        } else {
            result.push(left.shift());
        }
    }

    return result.concat(left).concat(right)
}

github算法地址