20

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

你会使用哪种排序算法？

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

如果您可以预期很多被比较的元素是相同的，比如说在 80% 的比较中，该怎么办。这有什么不同吗？

4

7 回答 7

11

Merge-insertion sort是插入排序的一种变体，被吹捧为几十年来已知比较最少的排序算法，并且可能仍然是用于最小比较的最佳自由记录排序算法：

合并插入排序是在n ≤ 15 或 20 ≤ n ≤ 22 时对n 个项目进行最小可能比较的排序算法，并且对于n ≤ 46 ，它具有最少的已知比较。

据报道， Glenn K. Manacher 的算法“以及后来的破纪录排序算法”（不幸的是，目前似乎都没有免费记录）适应合并插入排序算法以提供更少的比较。

于 2018-12-30T16:15:36.257 回答
9

获胜者是Sleep Sort，它不使用任何比较。

于 2012-10-26T18:50:47.540 回答
2

很可能是插入排序

正如他们所说，排序是其中的一个主题，魔鬼在细节中。通常，次要考虑因素支配着性能输入参数。

但是，如果比较非常昂贵并且如果大多数键是相同的，则输入可能被认为已经排序或几乎已经排序。

在这种情况下，您需要的是一种具有最快最佳情况的合理算法，并且几乎可以肯定是插入排序。

于 2012-10-26T18:56:44.827 回答
1

这取决于你有什么数据。您是否需要稳定的算法？

在您的数据统一的地方，您可以使用桶排序（Θ（n），O（n ^ 2））

计数排序（我认为这就是你要找的），它也是稳定的算法，但需要更多的内存（更少的是你有很多相同的记录）。

当然你可以使用睡眠排序，但是如果你有很多数据，它就不起作用了。

如果您的元素 80% 相同，也许有一种简单的方法可以说它们是相同的（完全相同）？

于 2012-10-26T19:04:37.207 回答
0

Shellsort使用较少的比较。

而且你有很多相同的元素，计数排序应该可以完成工作

于 2012-10-26T18:46:40.303 回答
0

也许像基数排序这样的非比较算法可能是答案，因为它在一般情况下也很快（需要时间 O(n)）。也不会在元素之间进行比较，但另一方面它需要大量内存

于 2020-12-15T23:54:55.267 回答
-1

分布排序（使用散列数组）几乎不需要比较。

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
于 2012-10-26T18:44:33.080 回答