Ank*_*deo 13 sorting algorithm
我在互联网上搜索哪种排序算法最适合非常大的数据集.我发现许多人认为合并排序是最好的,因为它是公平的,并且确保时间复杂度为O(n log n)并且快速排序不安全:快速排序的变体也可以不安全,因为真实的数据集可以是任何东西.
如果两个元素的交换具有可忽略的时间成本,那么为什么我们不能选择堆排序作为这种情况下的最佳排序算法,因为它与O(n log n)？一致.
在Merge排序的情况下,它需要另一个O(n)空间; 如果数据非常大,那么我们就不能使用这种算法.
请告诉我:在这种情况下哪种算法应该是最好的？
tem*_*def 47
没有一种算法显然是"最佳"算法.这取决于一系列因素.
首先,您可以将数据放入主内存吗？如果你不能,那么你需要依赖外部排序算法.这些算法通常基于quicksort和mergesort.
其次,您对输入分布有何了解？如果它主要是排序的,那么像Timsort这样的东西可能是一个很好的选择,因为它的设计可以很好地处理排序数据.如果它几乎是随机的,那么Timsort可能不是一个好选择.
第三,你在排序什么样的元素？如果要对通用对象进行排序,那么您几乎可以锁定比较排序.如果没有,也许您可以使用非比较排序,如计算排序或基数排序.
第四,你有多少核心？一些排序算法(quicksort,mergesort,MSD基数排序)非常好并行化,而其他排序算法(heapsort).
第五,您的数据如何表示？如果它们存储在数组中,则快速排序或快速排序变体可能会因为引用的位置而表现良好,而mergesort可能由于需要额外的内存而变慢.但是,如果它们在链表中,则来自quicksort的引用位置消失,mergesort再次突然变得具有竞争力.
最好的选择可能是考虑很多不同的因素,然后从那里做出决定.设计和研究算法如此有趣的原因之一是,很少有一个单一的最佳选择; 通常,最好的选择取决于您的具体情况和基于您所看到的变化.
(你在回答这个问题之前提到了一些关于quicksort,heapsort和mergesort的细节.虽然你认为quicksort有一个退化的O(n 2)最坏的情况,但有很多方法可以避免这种情况. .如果看起来快速排序会退化,那么introsort算法会跟踪递归深度并将算法切换到heapsort.这可以保证O(n log n)最坏情况下的行为具有较低的内存开销,并最大化您从中获得的好处.快速排序.随机快速排序,虽然仍然有O(n 2)最坏的情况,实际上击中最坏情况的可能性很小.
Heapsort在实践中是一个很好的算法,但在某些情况下没有其他算法那么快,因为它没有良好的参考局部性.也就是说,它永远不会退化并只需要O(1)辅助空间这一事实是一个巨大的卖点.
Mergesort确实需要很多辅助内存,这就是为什么在有大量数据需要排序时可能不想使用它的原因之一.但值得了解的是,因为它的变体被广泛使用.)
你的问题太开放了,无法具体回答.有许多有效的排序算法,每种算法都有自己的优点和缺点.如果您知道自己的数据,那么最佳效率算法(堆,快速,合并等)可能不是正确的工具.
例如,在最近的产品中,我们需要将书签保存在按其外观顺序排序的Word文档中.由于编辑文档(复制,剪切,粘贴),书签可能会变得未分类,因此在每次操作之后,使用列表非常重要.在这种情况下,bubblesort是正确的答案,即使它具有比任何数量的其他算法更高的大O复杂性.当列表几乎排序时(在这种情况下通常是这种情况)排序是有效的事实并且它是就地操作意味着它是适合该工作的工具.
仔细查看您的数据并阅读众所周知的排序算法的各种优点和缺点,您将很好地回答您自己的问题.