logo标签列表

哪种排序算法提供最佳的最坏情况性能？

algorithmsorting
4

什么是绝对最坏情况下已知的最快排序算法？我不关心最好情况，并且假设数据集非常大，如果这有任何影响。

3
请告诉我们更多关于您的具体情境，这样人们才能建议常用排序算法的优缺点。否则，我认为没有确定的答案。 - Brian Ensink
2
我建议你明确一下，你是否只关心大O符号，还是关心（ON log N）实现中涉及的常数。基数排序等算法会带来一些混淆，因为它们非常依赖于数据（而你的问题又过于简略）。 - ShuggyCoUk
如果一个算法的最坏情况复杂度是n^2，而另一个算法的复杂度是n-log-n，即使n^2 的情况非常罕见，后者在处理大数据集时仍然会更快。 - GBa
我建议将“+”改为“算法”，因为有多个候选项（只有在更多上下文中才相关的加号和减号）。 - ShuggyCoUk
@ted 我怀疑Greg会加上“使用最糟糕的初始输入”这个条件。 - ShuggyCoUk
显示剩余4条评论
16个回答
17

请确保您已经看过这个链接：

可视化排序算法 - 它帮助我决定了要使用哪种排序算法。

2
可视化排序算法是体验不同算法的绝佳方式，但也需要注意像 http://www.hatfulofhollow.com/posts/code/visualisingsorting/index.html 这样的内容。 - nevets1219
9

根据数据类型不同，排序的速度也会有所不同。例如对于整数（或任何可以表示为整数的值），最快的排序算法是基数排序，对于固定长度的值，其最坏情况复杂度为O(n)。而最好的通用比较排序算法的复杂度为O(n log n)。

+1 我刚意识到，如果N>10，这是最快的， 最优和最坏情况：O（n） - TStamper
7
如果您正在使用二进制比较，最好的排序算法需要O(N log N)次比较才能完成。 如果您正在寻找具有良好最坏情况性能的算法，则应查看MergeSort和HeapSort，因为它们在所有情况下都是O(N log N)算法。
如果所有数据都适合内存，则HeapSort很好，而MergeSort允许您更好地进行磁盘排序（但总体上需要更多空间）。
在维基百科排序算法页面上提到了其他一些不太知名的算法，它们都具有O(n log n)的最坏情况性能。（根据mmyers的评论）
6

对于预算无限的人

虽然有点幽默，但是正确的做法是： 排序网络用硬件空间换取比O(n log n)更好的排序效果！

如果不使用这种硬件（也很难获得），则最佳 比较排序 的下限是O(n log n)

O(n log n) 最坏情况下的性能（不考虑顺序）

超越n log n

如果你的数据适合这种方法，你可以超越n log n的限制，同时关注输入数据中的位数

基数排序和桶排序可能是最为知名的例子。如果没有更多关于你特定需求的信息，深入考虑这些方法也没有意义。

3

Quicksort通常是最快的排序算法，但如果你需要较好的最坏情况时间，可以尝试使用堆排序或归并排序。这两种算法在最坏情况下都具有O(n log n)的时间复杂度。

谢谢您提供了直接的答案，而不是让事情变得更加复杂。 - schlingel
2
如果你有一个巨大的数据集（比可用内存大得多），你可能会把数据存储在磁盘/磁带/需要昂贵随机访问的设备上，因此你需要进行外部排序。
在这种情况下，归并排序效果很好；与大多数其他排序不同，它不涉及随机读/写操作。
1

这主要与您的数据集大小以及该集合是否已经排序（或当前处于什么顺序）有关。

整本书都是关于搜索/排序算法的。假设最坏情况下没有“绝对最快”的排序方法，因为不同的排序方法具有不同的最坏情况。

1

这取决于大小，根据 大O符号 O(n)。

这里有一个排序算法的列表最好和最坏情况供您比较。 我更喜欢双向 MergeSort。

根据http://en.wikipedia.org/wiki/Sorting_algorithm，至少有六种比较排序算法具有O(n lg n)的最坏情况（这是理论最小值）。 - Michael Myers
返回翻译后的文本: true，链接显示有平局，但我更喜欢使用Mergesort来实现。 - TStamper
我的最爱也是归并排序。它是稳定的，保证了最坏情况下 O(n log n) 的性能，易于理解和编写，并且适用于不适合内存的大型数据集。 - Mark Ransom
1
如果您有足够大的数据集，您可能正在查看对数据的单个存储箱进行排序，然后使用归并排序来合并这些存储箱。但是此时，我们谈论的是数据集远远大于主内存的情况。
我想最正确的答案是“这取决于情况”。
1

这取决于数据类型和资源类型。例如，有些并行算法可以击败快速排序，但考虑到您提出的问题，您可能无法访问它们。有时一个算法的“最坏情况”对另一个算法来说是“最佳情况”（几乎排序好的数据对快速排序和归并排序来说是有问题的，但对更简单的技术来说很快）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接