想象一下两个元素的比较非常昂贵的情况。
您将使用哪种排序算法?
哪种排序算法在平均情况下使用最少的比较?
如果你能期望很多被比较的元素是相同的,比如说在80%的比较中。有什么不同吗?

最佳答案

很可能Insertion Sort
分类是其中一个主题,正如他们所说,魔鬼在细节。通常,次要考虑因素支配性能输入参数。
但是,如果比较非常昂贵,并且大多数键都相同,则可能认为输入已经排序或几乎已排序。
在这种情况下,您需要的是一个合理的算法,它具有最快的最佳情况,而且几乎肯定是an insertion sort.

10-06 05:24
查看更多