时间戳

首页 > 解决方案 > 选择排序：列表经过多少次排序后？

python - 选择排序：列表经过多少次排序后？

问题描述

在为即将到来的考试学习时，我发现了这个问题：

  1. 我们的排序代码完成了算法的所有遍历，即使列表在最后一次遍历之前已经排序。在列表上的选择排序算法经过多少次后，[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通过后我的名单会被排序。我究竟做错了什么？这只是一个选择题，没有任何背景，只有问题本身。

标签： pythonpython-3.xsorting

解决方案

第一步应该是从当前元素（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]

这里也是选择排序的一个很好的例子

推荐阅读