sunshine
管理员
管理员
  • 最后登录2023-10-30
  • 发帖数170
  • 社区居民
阅读:4465回复:0

[其它]【排序】归并排序--js实现

楼主#
更多 发布于:2020-02-11 21:54
思想
这是一种分治算法。将原始数组切分成较小的数组,直到每个小数组只有一项,然后在将小数组归并为排好序的较大数组,直到最后得到一个排好序的最大数组。如下图


图片:save.jpg


视频说明
https://www.bilibili.com/video/av88058418?from=search&seid=12615007212925523963


js代码实现:

function mergeSort(arr) {
    const length = arr.length;
    if (length === 1) { //递归算法的停止条件,即为判断数组长度是否为1
        return arr;
    }
    const mid = Math.floor(length / 2);
    const left = arr.slice(0,  mid);
    const right = arr.slice(mid, length);
    return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时,才开始归并
}
function merge(left, right) {
    const result = [];
    let il = 0;
    let ir = 0;
    //left, right本身肯定都是从小到大排好序的
    while( il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il]);
            il++;
        } else {
            result.push(right[ir]);
            ir++;
        }
    }
    //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
    while (il < left.length) { 
        result.push(left[il]);
        il++;
    }
    while(ir < right.length) {
        result.push(right[ir]);
        ir++;
    }
    return result;
}

代码参考:https://www.cnblogs.com/Bonnie3449/p/9574635.html
图片来自:https://segmentfault.com/a/1190000015488807

最新喜欢:

LiWangLiWang
游客


返回顶部

公众号

公众号