我在一本简略的书中读到了算法中的选择排序。书中出现了以下内容:
选择排序是所有排序算法中最慢的。它
重复执行几乎相同的任务而不学习任何东西
从一个迭代到下一个迭代。选择最大的元素max,
在A中进行n-1比较,并选择第二大元素
进行n-1比较-进展不大很多这样的比较
因为如果一个元素小于秒,它就不能
可能是最大的元素,因此对
最大值的计算。
粗体字是什么意思?
有人能用简单的例子来解释吗?
最佳答案
你这本书的作者似乎喜欢复杂的长句不要向他学习;已经有足够多的人知道如何迷惑他们的读者。
试图使其更易于理解:
当A具有n-1
元素时,从A中选择最大元素将进行n
比较不幸的是,排序算法没有重用这些信息。
当它再次启动内部循环以对其余元素进行排序时,它需要另一个n-2
比较(一个元素已与最后一个循环排序到正确的位置)。
由于sort在每次运行内部循环时只移动一个元素,因此大多数比较都会重复一次又一次,而不会对结果做任何处理—这只是浪费时间。
维基百科有一个nice animation how selection sort works。