algorithm - 为什么在选择排序中浪费了比较？

Question

我正在阅读Algorithms In A Nutshell书中的选择排序。书中出现以下内容：

选择排序是所有排序算法中最慢的。它重复执行几乎相同的任务，而不会从一次迭代到下一次迭代学习任何东西。选择 A 中最大的元素 max 进行 n-1 次比较，选择第二大元素进行 n-1 次比较 - 没有太大进展！许多这些比较都是浪费的，因为如果一个元素小于秒，它不可能是最大的元素，因此对最大值的计算没有影响。

粗体字是什么意思？

有人可以用简单的例子来解释吗？

Answer 1

您的书的作者似乎喜欢复杂、长句。不要向他学习；已经有足够多的人知道如何迷惑他们的读者。

试图使其更易于理解：

当 A 有元素时，从 A 中选择最大元素进行n-1比较n。不幸的是，排序算法没有重用任何这些信息。

当它再次启动内部循环以对剩余元素进行排序时，它需要进行另一次n-2比较（一个元素已与最后一个循环排序到正确的位置）。

由于每次运行内部循环时排序只移动一个元素，因此大多数比较都会一遍又一遍地重复，而不会对结果做任何事情——它们只是浪费时间。

维基百科有一个很好的动画选择排序是如何工作的。

Answer 2

考虑3,5,2,4,1。

最大的元素是5。第二大元素是4。

3小于4，因此它不能大于5，因此检查它是否本质上是一种浪费。