我最近在类里面学习了基本排序(冒泡排序、插入排序和选择排序)，并且对运行时间有点困惑。
老师给我们布置的作业中，有一个问题: “对于所有键都相同的文件，3 种基本排序中哪一种运行速度最快？对于数据顺序相反的文件呢？”
对于问题的第一部分，我不完全确定“键”的含义。那么，是不是意味着有一个大小为1的数组，有多个数据呢？我不认为“键”与“数据”相同。我知道如果所有数据都是有序的，那么插入排序将是最快的，但我不确定这是否会对问题产生任何影响。
对于问题的第二部分，我认为这将是选择排序，因为无论数据中的反转次数有多少，都需要进行恒定数量的比较。插入排序和冒泡排序会导致交换次数过多。我主要只是对问题的第一部分感到困惑。
最佳答案
通常，根据我的经验，在对文件进行排序时，可以说该文件由“记录”组成，并且您正在移动每条记录，以便它出现在它应该位于之前的所有记录之前。 “键”是您使用的记录的任何部分，以确定一个记录应该位于另一记录之前还是之后。如果您只是对数字或字符串进行排序，那么“键”就是整个记录。在其他情况下，每条记录可能是某人的学校成绩单，并且出于某种原因，您希望按学生姓名对这些记录进行排序，因此记录中的大部分数据不是键的一部分。如果您的老师已经说过他或她认为交换期间移动的数据单位是什么，将会很有帮助。
我认为您对记录已排序的情况的思考是正确的，并且所有相同的键就是这样一种情况。
对于记录顺序完全相反的情况，问题不在于选择排序中的比较次数受数据初始顺序的影响有多大；而在于选择排序的比较次数受数据初始顺序的影响。相反，问题(关于比较)是是否有任何算法能够比其他算法执行更少的任务。通常我们说插入排序比选择需要更少的比较，但在这种情况下，您可能可以以其他方式显示。当然，您还需要查看冒泡排序实际需要多少次比较。
关于algorithm - 基本排序运行时间比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23070962/