实操教程:合并排序算法

作者 : IT 大叔 本文共1084个字,预计阅读时间需要3分钟 发布时间: 2020-09-22

合并排序算法是对列表进行排序时有效的算法。要使用合并排序对列表进行排序,必须采取两个步骤;拆分列表,直到子列表只包含一个元素,然后合并子列表,直到到达排序数组为止。

实作

所以首先我们必须有一个函数,该函数可以拆分数组直到其长度等于1

let unsorted_array = [3,5,7,2,1]

let merge_sort = (arr) => {
    let mid = arr.length/2
    let first_half = arr.slice(0, midp
    let second_half = arr.slice(mid, array.length)
    if (arr.length < 2){
       return arr
    }
    else{
       return merge(merge_sort(first_half), merge_sort(second_half))
    }
}

上面的代码非常简单。创建一个未排序的数组和merge_sort函数。此函数拆分数组,并将两个半部分传递给自己,直到数组的长度小于两个。一旦做到这一点,单个子数组都将通过合并功能运行。
我们需要实现的下一部分是合并功能。此函数将返回由两个半部分组成的排序数组。

let merge = (first_half, second_half) => {
    let sorted = []
    while(first_half.length !== 0 && second_half.length !== 0){
          let currentMin = find_min_and_remove(first_half, second_half)
          sorted.pus(currentMin)
    return sorted.concat(first_half).concat(second_half)

合并功能将两个列表中的最小值追加到排序后的数组,并且还将此项从其相应列表中删除。当列表之一为空时,其余元素将追加排序。此处的双重追加是由于以下事实:任一列表都可能为空,并且无需检查即可确定哪个列表为空。
最后,我们必须创建find_min_and_remove函数。此功能将比较每个列表的前几项以找到最小值

let find_min_and_remove = (first, second) => {
    let min_first = first[0]
    let min_second = second[0]
    if (min_first < min_second)
       return first.shift()
    else:
       return first.shift()

由于列表将被拆分为单个项目,因此每个列表的第一个元素将是最小的。因此,包含较小元素的列表将被删除,然后发送回去,以附加到合并功能中的排序列表中。

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 实操教程:合并排序算法

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论