哪个排序算法使用最少的比较？ [英] Which sorting algorithm uses the fewest comparisons?

问题描述

想象一下，一个情况下，两个元素的比较是非常昂贵的。

Imagine a case where comparison of two elements is hugely expensive.

排序算法你会用哪一个？

Which sorting algorithm would you use?

哪个排序算法使用最少的比较在平均情况下？

Which sorting algorithm uses the fewest comparisons in the average case?

如果你可以期待很多比较的元素是相同的，说80％的比较。是否有所作为？

What if you can expect a lot of the compared elements to be identical, say in 80% of the comparisons. Does it make a difference?

推荐答案

排序是这些主题在哪里，他们说，魔鬼在细节中的一个。的通常情况下，二次考量主宰性能的输入参数。

Quite Possibly Insertion Sort

---

Sorting is one of those subjects where, as they say, the devil is in the details. Typically, secondary considerations dominate the performance input parameters.

然而，如果比较是非常昂贵的，如果最密钥是相同的，它是可能的输入可被视为已经排序或已经几乎排序

However, if comparisons are very expensive and if most keys are identical, it is possible that the input could be considered already sorted or already almost sorted.

在这种情况下，你想要的是一个合理的算法，具有最快的最好的情况下，的，而且几乎肯定会的 插入排序的。

In that case, what you want is a reasonable algorithm that has the fastest best case, and that would almost certainly be an insertion sort.

这篇关于哪个排序算法使用最少的比较？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！