选择排序内层循环的开始值
来源：1-2 实现选择排序法
大唐小神
2020-07-15 14:44:34
选择排序内层循环的开始值 j = i + 1 是否更好些呢，(整理问题)内层循环的本质上是在[j=i,n)无序区间中拿j和j之后的每一个元素进行比较找出最值，所以j=i开始的话就有一次是和自己比较了，不知道我理解的对么~语言为kotlin
for (i in arr.indices) {
//在剩余的元素中找到比arr[minIndex]还小的元素 有则交换
//即每次遍历 就是找到剩余最小元素的下标
var minIndex = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIndex])
minIndex = j
}
swap(arr, i, minIndex)
}写回答
2回答
-
你理解的完全正确。j 从 i + 1 开始是完全没问题的。如果 j 从 i 开始，确实会自己和自己进行一次比较。（因为 minIndex 初始值为 i）。在课程中，我写成从 i 开始，是为了和循环不变量的语义做对应。即从 arr[i...n)中去找最小值，所以我从 i 开始搜索。
其实这样的点，在程序设计中还有很多。比如在选择排序中，i < arr.length 也可以改成 i + 1 < arr.length，因为 i 取到 arr.length - 1 的时候，只有一个元素了，它一定已经是最大值了。
在这个课程的代码中，对于这些点，我没有过度的去“扣”，主要还是因为，这些并非是算法设计的重点。课程后续，就会看到，这种级别的优化，再怎么优化，都永远拼不过复杂度级别的优化。面对百万级别的数据，选择排序的思路无论怎么优化，都是招架不住的；但是更高级的排序算法，则可以瞬间给出结果。这种算法的优化，将是这个课程关注的重点。这一点，我在课程后续还会强调的：
不过还是谢谢你的提醒。赞思考！
继续加油！：）
11 -
假蛙工程师
2021-10-16
老师真6，从语义上，arr[0, i)是已排序，arr[i, n) 是未排序，从未排序的元素中找出最小的元素，的确可以遍历一遍。
0
相似问题