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

[Rhianu]

下面是用 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
    	}
	}
}

[BBrother]

这个是冒泡，每次比较的是相邻的元素

[IGJacklove]

你这会数组越界吧？。。

[Rhianu]

@BBrother 我起初也是这样想，但是有点困惑的是冒泡排序的话，是对比相邻的两个值。而这种排序 arr[i] 中的 i 最初值 是 0，在内循环中 i 是跟每一个值都对比一次后确定绝对最小值后，才进行的下一轮外部循环。

[wander639]

感觉还是插入排序吧，当前元素与剩下未排序中最小的交换

[Rhianu]

@IGJacklove 刚才打印了一下，确实越界了，多谢提醒

[mtmax]

像选择

[piapia123]

我觉得是冒泡，常见的冒泡是 [往后冒] ，这歌是 [往前冒]

[lzlee]

能排出来, 但是 j + 1 会越界

我怎么觉得则会个更接近与 选择排序

[lovecy]

这不就是选择排序么，每次 j 循环找到最小的，放到 i 的位置。
说冒泡和插入的有看代码么。。

[lovecy]

let j = i+1;
..
const b = arr[j];
...
arr[i] = b
arr[j] = a
改成这样就能不越界了，j<length 会自动判断的

[Rhianu]

@mtmax @lovecy 看了下选择排序的定义，再结合实现的逻辑确实是选择排序无疑了。 😂 本来我是看着插入排序的动画实现的，没想到阴差阳错实现成了选择排序，见笑了。谢谢大家的帮助！

[Rhianu]

@piapia123 我刚开始也是以为是冒泡的一种，但冒泡是对比相邻两个值，是在内部循环中的对比。而实现的过程确是 i 跟 j （外部和内部）的对比，已经不是相邻的两个值了，内部的每次循环都能得到一个比 i 大或者小的绝对值出来，而冒泡是相邻的大小，并不是绝对，而符合这种绝对值对比的，是选择排序算法。

[BBrother]

@Rhianu 看差了，确实是选择

[hdbzsgm]

排序意义实际上是有严格区分的:
冒泡 /选择排序是每轮在所有输入中选出 min/max 的值进行排序。区别是冒泡会交换元素, 选择会记录位置。
插入排序则是按顺序排序部分已知的输入, 直到输入结束, 这个过程可以参考打牌时摸牌理理的过程。

[hdbzsgm]

@hdbzsgm 摸牌理理 -> 摸牌整理

[swordspoet]

可以从打扑克牌的角度去理解选择排序，在打牌的时候有的人喜欢把所有的牌都摸到手上之后再整理牌的顺序，从第一张牌开始，找到剩下所有牌里面找到一张最大（或者最小）的牌放在第一的位置，然后第二张牌也是按照这种排序方法。

[jinliming2]

代码里有越界 bug 。
这是选择排序。
楼上说冒泡的估计是看岔了，冒泡是相邻两个比较、相邻两个交换。
而这个代码是固定和 a[i] 交换，就变成选择了。

[Rhianu]

@jinliming2 是的，数组越界已修复，多谢指正

[bruce0]

@lovecy 我看也是选择排序,首先排除插入,插入排序是从未排序的元素和已排序的元素比较. 这个虽然看起来像冒泡,都是两两比较,但是冒泡是 i 随着 j 一起移动的, 但是这个的 i 在第二层循环中是固定的

[lambdafate]

是选择排序啊！！！

冒泡会比较相邻的两个元素
插入排序会把一个元素插入到已经有序的序列中
选择排序每次会在未排序的序列中选择一个最大值或最小值