CGLib动态代理 Redis CPU sqlite swing datetime matplotlib server insert bootstrap后台管理模板 nginx视频教程 ppt视频教程下载 click事件 js获取月份 安卓程序源代码 python计算器 python基础教程 python开发界面 javatrim stringjava java发邮件 java的方法 java基础框架 java代码 linux的find linux启动 ntscan 摩尔斯电码翻译器 编辑软件 backtrack4 asp编程 cad乘号 sql2008r2 文件批量更名 优酷app播放器下载 ps怎么做漂亮艺术字 熊猫头表情包制作 ps旋转图层 cad代理信息 戴尔键盘灯怎么开
当前位置: 首页 > 学习教程  > 编程语言

归并排序讲解

2020/10/16 17:48:34 文章标签:

算法本质 把长度为n的输入序列分成两个长度为n/2的子序列;对这两个子序列分别采用归并排序,直到两个子序列的长度为1,无法分隔为止。比较左边序列的第一个元素与右边序列的第一个元素的大小,小的放入结果集。当左右序列中某一个序…

算法本质

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序,直到两个子序列的长度为1,无法分隔为止。
  3. 比较左边序列的第一个元素与右边序列的第一个元素的大小,小的放入结果集。
  4. 当左右序列中某一个序列没有元素了,将剩下的那个序列与结果集合并变为新的结果集
  5. 重复3,4这个过程,直到将所有的序列合并为一个结果集为止。

实例讲解

初始数据: [1,4,3,2,7,6,5]
分隔为两个子序列:	
[1,4,3] [2,7,6,5] => [1,[4,3]] [[2,7],[6,5]]
 => [1,[[4],[3]]]  [[[2],[7]],[[6],[5]]]
归并:
[1,[3,4]] [[2,7],[5,6]] => [1,3,4] [2,5,6,7] => [1,2,3,4,5,6,7]

取一小部分详细解析:
[[2,7],[5,6]] => 结果集中:[2] => [2,5] =>[2,5,6] =>[2,5,6,7](左边剩下的都放到结果集中)

代码(附详细注解)

/*
* 归并排序,该程序为为从小到大排列
* */

//归并
function merge(left,right) {
    var result = [];
    //当左右两边的数据还没有出现填充完毕的情况时
    while (left.length>0 && right.length>0){
        //如果左边的头部大于右边的,将右边的头部加入到结果集,反之将左边头部加入到结果集
        if(left[0] >= right[0]){
            result.push(right.shift())
        }else{
            result.push(left.shift())
        }
    }
    left.length == 0 ? result = result.concat(right) : 0;
    right.length == 0 ? result = result.concat(left) : 0;
    return result;
}

//归并排序
function mergeSort(arr) {
    let len = arr.length;
    if(len < 2){
        return arr;
    }else{
        //获取数组的中间值,向下取整
        let mid = Math.floor(len / 2 );
        //获取左边的数据
        let left = arr.slice(0,mid);
        //获取右边的数据
        let right = arr.slice(mid)
        //递归调用将数据分隔到单个为止,逐步调用合并函数
        return merge(mergeSort(left),mergeSort(right));
    }
}

console.log(mergeSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))


本文链接: http://www.dtmao.cc/news_show_300192.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?