algorithm - 基本排序运行时间比较

Question

我最近在类里面学习基本排序(冒泡排序、插入排序和选择排序)，但对运行时间有点困惑。

在老师给我们的作业中，有一个问题是:“对于所有键都相同的文件，3 种基本排序中哪一种运行速度最快？对于数据顺序相反的文件呢？”

对于问题的第一部分，我不完全确定“键”是什么意思。那么，是不是说存在一个大小为1的数组，里面有多个数据呢？我不认为“ key ”与“数据”相同。我知道如果所有数据都是有序的，那么插入排序将是最快的，但我不确定这是否会对问题产生任何影响。

对于问题的第二部分，我认为这将是选择排序，因为无论数据中的倒置次数如何，它都会进行恒定次数的比较。插入排序和冒泡排序会导致交换过多。

我主要只是对问题的第一部分感到困惑。

Answer 1

通常根据我的经验，在对文件进行排序时，可以说该文件由“记录”组成，并且您正在移动每条记录，以便它出现在它应该出现在所有记录之前。 “键”是您使用的记录的任何部分，以确定一条记录应该在另一条记录之前还是之后。如果您只是对数字或字符串进行排序，那么“键”就是整条记录。在其他情况下，每条记录可能是某人的学校成绩单，出于某种原因，您希望按学生姓名对这些记录进行排序，因此记录中的大部分数据都不是键的一部分。如果您的老师已经说明了他或她认为是交换期间移动的数据单元，将会很有帮助。

我认为您对记录已经排序的情况的思考是正确的，并且所有键都相同就是这样一种情况。

对于记录完全相反顺序的情况，问题不在于选择排序中的比较次数受数据初始顺序的影响有多大；相反，问题(关于比较)是是否有任何算法能够比其他算法执行得更少。通常我们说插入排序比选择需要更少的比较，但在这种情况下，您可以显示其他情况。当然，您还需要查看冒泡排序实际需要进行多少次比较。