我最近在课堂上学习了一些基本排序(气泡排序、插入排序和选择排序),并且对运行时间有点困惑。
在老师给我们布置的作业上,有一个问题问我们:
“对于所有密钥相同的文件,三种基本排序中哪一种运行最快?对于数据顺序相反的文件呢?”
对于问题的第一部分,我不完全确定“钥匙”是什么意思。那么,这是否意味着存在一个1大小的数组,其中包含多个数据?我认为“键”和“数据”不一样。我知道如果所有的数据都是有序的,那么插入排序将是最快的,但我不确定这是否会对问题有任何影响。
对于问题的第二部分,我认为这将是选择排序,因为无论数据中的倒数是多少,这都需要固定数量的比较插入排序和冒泡排序会导致交换过多。
我对问题的第一部分感到困惑。

最佳答案

通常以我的经验,当对一个文件进行排序时,可以说该文件由“记录”组成,并且您正在移动每个记录,以便它出现在它应该出现在的所有记录之前“键”是您正在使用的记录的任何部分,以确定一个记录应该在另一个记录之前还是之后。如果只是对数字或字符串进行排序,那么“key”就是整个记录。在其他情况下,每个记录可能是某人的学校成绩单,出于某种原因,您希望根据学生的姓名对这些记录进行排序,因此记录中的大多数数据不是密钥的一部分。如果你的老师说了他或她认为是交换过程中移动的数据单位,这会很有帮助。
我认为您正确地考虑了记录已经排序的情况,所有相同的键都是一个这样的情况。
对于记录的顺序正好相反的情况,问题不在于选择排序中的比较次数受数据初始顺序的影响有多大;而在于(关于比较的)任何算法是否能够比其他算法执行得更少通常我们说插入排序比选择排序需要的比较少,但是在这种情况下,您可以显示其他内容。当然,您还需要看看Bubble Sort实际需要多少比较。

09-17 21:03
查看更多