V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Rhianu
V2EX  ›  程序员

请教大家一个基础的算法问题

  •  
  •   Rhianu ·
    haojen · 2020-11-21 11:24:02 +08:00 · 2676 次点击
    这是一个创建于 1223 天前的主题,其中的信息可能已经有所发展或是发生改变。

    下面是用 js 实现的排序算法,将无序的数组按照从小到大的顺序排序。请问这种算是插入排序吗? 如果不是,这种算什么算法?

    const arr = [4, 2, 3, 1, 5, 9, 6, 10, 7, 8]
    const length = arr.length
    
    for(let i = 0; i < length; i++) {
        for(let j = i; j < length; j++) {
            const a = arr[i]
            const b = arr[j + 1]
            if(b < a) {
                arr[i] = b
                arr[j + 1] = a
        	}
    	}
    }
    
    24 条回复    2020-11-22 11:27:02 +08:00
    BBrother
        1
    BBrother  
       2020-11-21 11:30:07 +08:00
    这个是冒泡,每次比较的是相邻的元素
    IGJacklove
        2
    IGJacklove  
       2020-11-21 11:38:18 +08:00 via Android
    你这会数组越界吧?。。
    Rhianu
        3
    Rhianu  
    OP
       2020-11-21 11:41:05 +08:00
    @BBrother 我起初也是这样想,但是有点困惑的是冒泡排序的话,是对比相邻的两个值。而这种排序 arr[i] 中的 i 最初值 是 0,在内循环中 i 是跟每一个值都对比一次后确定绝对最小值后,才进行的下一轮外部循环。
    wander639
        4
    wander639  
       2020-11-21 11:45:54 +08:00
    感觉还是插入排序吧,当前元素与剩下未排序中最小的交换
    Rhianu
        5
    Rhianu  
    OP
       2020-11-21 11:46:57 +08:00
    @IGJacklove 刚才打印了一下,确实越界了,多谢提醒
    mtmax
        6
    mtmax  
       2020-11-21 11:47:16 +08:00   ❤️ 1
    像选择
    piapia123
        7
    piapia123  
       2020-11-21 11:49:42 +08:00
    我觉得是冒泡,常见的冒泡是 [往后冒] ,这歌是 [往前冒]
    lzlee
        8
    lzlee  
       2020-11-21 11:52:10 +08:00
    能排出来, 但是 j + 1 会越界

    我怎么觉得则会个更接近与 选择排序
    lovecy
        9
    lovecy  
       2020-11-21 11:52:36 +08:00   ❤️ 2
    这不就是选择排序么,每次 j 循环找到最小的,放到 i 的位置。
    说冒泡和插入的有看代码么。。
    lovecy
        10
    lovecy  
       2020-11-21 11:54:46 +08:00   ❤️ 1
    let j = i+1;
    ..
    const b = arr[j];
    ...
    arr[i] = b
    arr[j] = a
    改成这样就能不越界了,j<length 会自动判断的
    Rhianu
        11
    Rhianu  
    OP
       2020-11-21 11:58:27 +08:00
    @mtmax @lovecy 看了下选择排序的定义,再结合实现的逻辑确实是选择排序无疑了。 😂 本来我是看着插入排序的动画实现的,没想到阴差阳错实现成了选择排序,见笑了。谢谢大家的帮助!
    Rhianu
        12
    Rhianu  
    OP
       2020-11-21 12:03:18 +08:00
    @piapia123 我刚开始也是以为是冒泡的一种,但冒泡是对比相邻两个值,是在内部循环中的对比。而实现的过程确是 i 跟 j (外部和内部)的对比,已经不是相邻的两个值了,内部的每次循环都能得到一个比 i 大或者小的绝对值出来,而冒泡是相邻的大小,并不是绝对,而符合这种绝对值对比的,是选择排序算法。
    BBrother
        13
    BBrother  
       2020-11-21 12:33:02 +08:00
    @Rhianu 看差了,确实是选择
    hdbzsgm
        14
    hdbzsgm  
       2020-11-21 13:09:07 +08:00
    排序意义实际上是有严格区分的:
    冒泡 /选择排序是每轮在所有输入中选出 min/max 的值进行排序。区别是冒泡会交换元素, 选择会记录位置。
    插入排序则是按顺序排序部分已知的输入, 直到输入结束, 这个过程可以参考打牌时摸牌理理的过程。
    hdbzsgm
        15
    hdbzsgm  
       2020-11-21 13:09:31 +08:00
    @hdbzsgm 摸牌理理 -> 摸牌整理
    swordspoet
        16
    swordspoet  
       2020-11-21 13:31:48 +08:00
    可以从打扑克牌的角度去理解选择排序,在打牌的时候有的人喜欢把所有的牌都摸到手上之后再整理牌的顺序,从第一张牌开始,找到剩下所有牌里面找到一张最大(或者最小)的牌放在第一的位置,然后第二张牌也是按照这种排序方法。
    jinliming2
        17
    jinliming2  
       2020-11-21 14:04:35 +08:00
    代码里有越界 bug 。
    这是选择排序。
    楼上说冒泡的估计是看岔了,冒泡是相邻两个比较、相邻两个交换。
    而这个代码是固定和 a[i] 交换,就变成选择了。
    Rhianu
        18
    Rhianu  
    OP
       2020-11-21 16:36:43 +08:00
    @jinliming2 是的,数组越界已修复,多谢指正
    bruce0
        19
    bruce0  
       2020-11-21 17:00:02 +08:00
    @lovecy 我看也是选择排序,首先排除插入,插入排序是从未排序的元素和已排序的元素比较. 这个虽然看起来像冒泡,都是两两比较,但是冒泡是 i 随着 j 一起移动的, 但是这个的 i 在第二层循环中是固定的
    lambdafate
        20
    lambdafate  
       2020-11-21 17:09:10 +08:00
    是选择排序啊!!!

    冒泡会比较相邻的两个元素
    插入排序会把一个元素插入到已经有序的序列中
    选择排序每次会在未排序的序列中选择一个最大值或最小值
    akira
        21
    akira  
       2020-11-21 22:13:05 +08:00
    这样的话 应该就是冒泡了

    const a = arr[j] <=== 换成 j
    const b = arr[j + 1]
    autogen
        22
    autogen  
       2020-11-22 10:44:45 +08:00
    @BBrother 不是比较相邻元素,每次取[i+1,length)最小的元素放到 i,所以这个是选择排序
    BBrother
        23
    BBrother  
       2020-11-22 11:00:37 +08:00
    @autogen 我看差了,把 i 看成 j 了
    DEVN
        24
    DEVN  
       2020-11-22 11:27:02 +08:00 via iPhone
    一层就够了吧!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1667 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 72ms · UTC 16:46 · PVG 00:46 · LAX 09:46 · JFK 12:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.