我最近在课堂上学习了基本排序（气泡排序，插入排序和选择排序），并且与运行时间有点混淆。小学排序运行时间比较
在老师给我们的作业上，一个问题问： “3个基本排序中哪一个对所有键完全相同的文件运行速度最快？对于具有相反数据的文件，怎么办？
对于问题的第一部分，我不完全确定他们是什么意思的“钥匙”。那么，这是否意味着有一个包含多个数据的大小为1的数组？我不认为“键”与“数据”是一样的。我知道如果所有的数据都是有序的，那么插入排序会是最快的，但我不确定这会对问题产生什么影响。
对于问题的第二部分，我认为这将是选择排序，因为无论数据中的反转次数如何，都需要进行不断的比较。插入排序和冒泡排序会导致交换过多。
我大多只是对问题的第一部分感到困惑。
通常根据我的经验，在对文件进行排序时，可以说文件由“记录”组成，并且您正在移动每条记录，以使其出现在它应该在之前的所有记录之前。 “关键”是您正在使用的记录的任何部分，以确定一条记录应该在另一条记录之前还是之后。如果您只是对数字或字符串进行排序，那么“键”就是整个记录。在其他情况下，每条记录可能是某人的学校成绩单，出于某种原因，您希望按照学生的姓名对这些记录进行排序，因此记录中的大部分数据都不是关键的一部分。如果您的老师已经说过他或她认为是交换过程中移动的数据单元，那将会有所帮助。
我认为你正在考虑关于记录已经排序的情况，所有相同的密钥就是这种情况。
对于记录顺序完全相反的情况，问题并不在于选择排序的比较次数受数据初始顺序影响的程度;相反，问题（关于比较）是，任何算法能否比其他算法执行更少。通常我们说插入排序的比较比选择少，但在这种情况下，您可能会显示其他内容。当然，你也需要看看泡沫排序实际需要多少次比较。
你的老师的问题是：
其中的3种基本的运行速度最快的文件具有相同的所有键？
换句话说，问题是：
其中3个基本各种各样的具有最小时间复杂度为最佳的案例？
时间复杂度：一个渐近数学符号，表示运行时间与输入大小相关的增长率。
最佳案例：该列表已经排序，这包括相同条目的情况。
3个基本类别是什么？
插入排序与O(n)的最佳案例。
选择种类与O(n^2)最佳案例。
料斗分类与O(n+k)对最佳案例。
所以在最好的情况下最好的基本排序算法是与O(n)插入排序。
你在正确的轨道上。当被排序的集合中的所有内容都是相同的[['a'，'a'，'a'，'a'，..]'，即不交换时，哪个算法是最快的。当设置为倒序时，哪个算法最快，即。许多掉期。 – deanosaur
因此插入排序为第一个，并选择第二个？ – user3421510
我认为你是正确的插入排序会很好，当几乎没有掉期，也就是说，当集合已经大多数排序。当有大量掉期交易时，您的选择排序可能会更好。但是，除非您使用小数据集，否则这两个算法都不会执行mergesort。 – deanosaur