南昌网络公司,南昌网站建设,南昌APP开发,南昌小程序开发,南昌网络推广,南昌网络营销,网络公司,网络营销,网站推广,网站优化,网站制作,网站设计,网站建设,百度SEO优化,小程序开发,公众号开发,APP开发,全网推广,网站制作,网页制作,高端网站设计,高端网站建设,南顺网络,南顺科技
当前位置 南顺网络>> 知识拓展

js归并排序

1. 案例

将数组 [8,4,7,5,1,3,6,2] 使用归并排序法按顺序排序成为数组 [1,2,3,4,5,6,7,8] 

2. 思路

第一步:按照二分查找法一步步拆分。

先将 8,4,7,5,1,3,6,2 拆分成 [8,4,7,5] 和 [1,3,6,2]。

再分别将 8,4,7,5 拆分成 [8,4] 和 [7,5];1,3,6,2 拆分成 [1,3] 和 [6,2]。

进一步拆分成[8],[4];[7],[5];[1],[3];[6],[2]。


第二步:按照先后顺序一步步组合。

使用循坏将组内第一个元素按照升序比较并删除,第二个元素则成为了第一个元素。继续升序比较并删除。分别得到:

第一轮数组比较:[4,8];

第二轮数组比较:[5,7];

第三轮数组比较:[4,5,7,8];

第四轮数组比较:[1,3];

第五轮数组比较:[2,6];

第六轮数组比较:[1,2,3,6,8];

第七轮数组比较:[1,2,3,4,5,6,7,8];


3. 代码

var arr=[8,4,7,5,1,3,6,2];

function sort(arr) {

    if (arr.length < 2) {

        return arr;

    }

    var length = Math.round(arr.length/2);//四舍五入取对半长度的整数

    var right = arr.splice(length);

    var left = arr;

    return merge(sort(left), sort(right))

};

function merge(left, right) {

    var result = [];

    //因为两个数组内的顺序相同,所以只需要对比每个数组的首元素,小的先push,大的后push。

    while (left && left.length && right && right.length) {

        if (left[0] <= right[0]) {

            result.push(left.shift());

        } else {

            result.push(right.shift());

        }

    }

    //剩余的直接添加到数组中

    if (left && left.length) {

          result = [...result,...left];

    }

    if (right && right.length) {

          result = [...result,...right];

    }

    return result;

}

console.log(sort(arr));//[1,2,3,4,5,6,7,8]

————————————————

版权声明:本文为CSDN博主「杏子_1024」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

原文链接:https://blog.csdn.net/weixin_44135121/article/details/103499061