选择排序:在经过多少次传递之后，列表将被排序？
选择排序:在经过多少次传递之后，列表将被排序？
提问于 2018-12-15 18:31:52
在为即将到来的考试做准备时，我发现了以下问题：
- 我们的排序代码完成了算法的所有传递，即使列表在最后一次传递之前被排序。在列表
[9, 8, 6, 4, 3, 1]上的选择排序算法传递了多少次之后，我们可以因为列表已经排序而停止吗？
根据我对Selection Sort Algorithm的理解，我的答案是7
[9, 8, 6, 4, 3, 1]
[9, 8, 6, 4, 3, 1]
[8, 9, 6, 4, 3, 1]
[6, 8, 9, 4, 3, 1]
[4, 6, 8, 9, 3, 1]
[3, 4, 6, 8, 9, 1]
[1, 3, 4, 6, 8, 9]但根据我的指导员，在3通过后，我的名单将被排序。我做错了什么？这只是一个选择题，没有任何背景，但问题本身。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-12-15 20:03:39
第一步应该是从当前元素(9)中找到数组(1)中的最小数目并切换它们的位置，第二步应该是找到下一个最小元素(3)，并与数组(8)中的下一个元素切换，等等。该算法的工作原理是与数组中尚未排序的所有元素进行比较，因此运行时是最糟糕的O(n^2)。
如: 9，8，6，4，3，1,1，8，6，4，3，9,1，3，6，4，8，9,1，3，4，6，8，9，1，3，4，6，8，9
这里也是动作中选择排序的一个很好的例子
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53796089
复制相关文章
相似问题
腾讯云开发者
