这是一个创建于 1461 天前的主题，其中的信息可能已经有所发展或是发生改变。
下面是用 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
}
}
}
 |
1
BBrother 2020-11-21 11:30:07 +08:00
这个是冒泡，每次比较的是相邻的元素
|
 |
2
IGJacklove 2020-11-21 11:38:18 +08:00 via Android
你这会数组越界吧？。。
|
 |
3
Rhianu OP @BBrother 我起初也是这样想，但是有点困惑的是冒泡排序的话，是对比相邻的两个值。而这种排序 arr[i] 中的 i 最初值 是 0，在内循环中 i 是跟每一个值都对比一次后确定绝对最小值后，才进行的下一轮外部循环。
|
 |
4
wander639 2020-11-21 11:45:54 +08:00
感觉还是插入排序吧，当前元素与剩下未排序中最小的交换
|
|
5
Rhianu OP @IGJacklove 刚才打印了一下，确实越界了，多谢提醒
|
 |
6
mtmax 2020-11-21 11:47:16 +08:00  1
像选择
|
 |
7
piapia123 2020-11-21 11:49:42 +08:00
我觉得是冒泡，常见的冒泡是 [往后冒] ，这歌是 [往前冒]
|
 |
8
lzlee 2020-11-21 11:52:10 +08:00
能排出来, 但是 j + 1 会越界
我怎么觉得则会个更接近与 选择排序 |
 |
9
lovecy 2020-11-21 11:52:36 +08:00 2
这不就是选择排序么，每次 j 循环找到最小的，放到 i 的位置。
说冒泡和插入的有看代码么。。 |
|
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 会自动判断的 |
|
11
Rhianu OP |
|
12
Rhianu OP @piapia123 我刚开始也是以为是冒泡的一种，但冒泡是对比相邻两个值，是在内部循环中的对比。而实现的过程确是 i 跟 j （外部和内部）的对比，已经不是相邻的两个值了，内部的每次循环都能得到一个比 i 大或者小的绝对值出来，而冒泡是相邻的大小，并不是绝对，而符合这种绝对值对比的，是选择排序算法。
|
 |
14
hdbzsgm 2020-11-21 13:09:07 +08:00
排序意义实际上是有严格区分的:
冒泡 /选择排序是每轮在所有输入中选出 min/max 的值进行排序。区别是冒泡会交换元素, 选择会记录位置。 插入排序则是按顺序排序部分已知的输入, 直到输入结束, 这个过程可以参考打牌时摸牌理理的过程。 |
 |
16
swordspoet 2020-11-21 13:31:48 +08:00
可以从打扑克牌的角度去理解选择排序，在打牌的时候有的人喜欢把所有的牌都摸到手上之后再整理牌的顺序，从第一张牌开始，找到剩下所有牌里面找到一张最大（或者最小）的牌放在第一的位置，然后第二张牌也是按照这种排序方法。
|
 |
17
jinliming2 2020-11-21 14:04:35 +08:00
代码里有越界 bug 。
这是选择排序。 楼上说冒泡的估计是看岔了，冒泡是相邻两个比较、相邻两个交换。 而这个代码是固定和 a[i] 交换，就变成选择了。 |
|
18
Rhianu OP @jinliming2 是的，数组越界已修复，多谢指正
|
 |
19
bruce0 2020-11-21 17:00:02 +08:00
@lovecy 我看也是选择排序,首先排除插入,插入排序是从未排序的元素和已排序的元素比较. 这个虽然看起来像冒泡,都是两两比较,但是冒泡是 i 随着 j 一起移动的, 但是这个的 i 在第二层循环中是固定的
|
 |
20
lambdafate 2020-11-21 17:09:10 +08:00
是选择排序啊！！！
冒泡会比较相邻的两个元素 插入排序会把一个元素插入到已经有序的序列中 选择排序每次会在未排序的序列中选择一个最大值或最小值 |
 |
21
akira 2020-11-21 22:13:05 +08:00
这样的话 应该就是冒泡了
const a = arr[j] <=== 换成 j const b = arr[j + 1] |
 |
24
DEVN 2020-11-22 11:27:02 +08:00 via iPhone
一层就够了吧！
|
Select Language