想象一下两个元素的比较非常昂贵的情况。
你会使用哪种排序算法？
在一般情况下，哪种排序算法使用最少的比较？
如果您可以预期很多比较元素是相同的，比如80％的比较，那该怎么办呢？这有什么不同吗？
想象一下两个元素的比较非常昂贵的情况。
你会使用哪种排序算法？
在一般情况下，哪种排序算法使用最少的比较？
如果您可以预期很多比较元素是相同的，比如80％的比较，那该怎么办呢？这有什么不同吗？
排序是其中一个主题，正如他们所说， 细节决定成败。 通常，次要考虑因素主导性能输入参数。
但是，如果比较非常昂贵并且如果大多数密钥相同，则可能认为输入已经排序或已经几乎排序。
在这种情况下，你想要的是一个最快的合理算法 最好的情况， 这几乎可以肯定 插入排序。
获胜者是 睡觉排序，没有使用比较。
这取决于你拥有什么数据。你需要稳定的算法吗？
在您的数据统一的情况下，您可以使用桶排序（Θ（n），O（n ^ 2））
数排序 （我认为这是你正在寻找的），它也是稳定的算法，但需要更多的内存（少了你有很多相同的记录）。
当然你可以使用Sleep排序，但如果你有很多数据它将无法使用。
如果你的元素在80％相同，也许有一种简单的方法可以说有相同的（只是相同的）？
分发排序（使用散列数组）几乎不进行比较。
m = max number may appear in the input + 1
hash = array of size m
initialize hash by zeroes
for i = 0 to n - 1
hash[input[i]] = hash[input[i]] + 1
j = 0
for i = 0 to m - 1
while hash[i] > 0
sorted[j] = i
j = j + 1
hash[i] = hash[i] - 1