通用且实用的排序算法比O(n log n)更快? [英] Generic and practical sorting algorithm faster than O(n log n)?

问题描述

是否有比O(n log n)运行得更快的通用元素实用算法(与计数排序或存储桶排序不同)?

Is there any practical algorithm for generic elements (unlike counting sort or bucket sort) that runs faster than O(n log n)?

推荐答案

许多人都提到了信息理论Ω(n lg n)绑定在比较排序算法上，在比较排序中不能被打破. (之前的问题探讨了为什么会这样.)

Many people have mentioned the information-theoretic Ω(n lg n) bound on comparison sorting algorithms, which can't be broken in comparison sorts. (This earlier question explores why that's the case.)

但是，有些比较排序类型虽然在平均情况下不破坏O(n lg n)，但可以证明在某种程度上已经预先排序的输入上运行得更快.例如，Dijkstra的smoothsort在O(n)上对已排序的输入(具有O(n lg n)最坏情况的行为)运行.我最喜欢的一种排序方法笛卡尔树排序可证明在某些情况下充分利用了预排序的优势指标.例如，它可以对时间常数为O(n)的子序列具有递增或递减的任何序列进行排序，在最坏的情况下，它可以优雅地降级为O(n lg n).

However, there are some types of comparison sorts that, while not breaking O(n lg n) in the average case, can be shown to run faster on inputs that are already presorted to some extent. For example, Dijkstra's smoothsort runs in O(n) on already-sorted inputs with O(n lg n) worst-case behavior. One of my favorite sorts, Cartesian tree sort, provably takes optimal advantage of presortedness in a few metrics. For example, it can sort any sequence with a constant number of increasing or decreasing subsequences in time O(n), degrading gracefully to O(n lg n) in the worst case.

关于非比较排序的问题，有一些著名但棘手的整数排序算法，这些整数通过np进行巧妙的位操作技巧而超过O(n lg n).最著名的整数排序算法是可以以O(n lg lg n)进行排序的随机算法，而最快的确定性排序算法是在O(n lg lg n)的时间内运行.您可能已经听说过基数排序在O(n)中起作用，尽管从技术上讲它是O(n lg U)，其中U是要排序的数组中的最大值.

On the subject of non-comparison sorts, there are some famous but tricky sorting algorithms for integers that surpass O(n lg n) bynp doing clever bit-manipulation tricks. The best known integer sorting algorithm is a randomized algorithm that can sort in O(n √lg lg n), while the fastest deterministic algorithm for integer sorting runs in O(n lg lg n) time. You may have heard that radix sort works in O(n), though technically it's O(n lg U), where U is the largest value in the array to sort.

简而言之，不，您不能做得比O(n lg n)好得多，但是如果您对输入有所了解，就可以做得更好.

In short, no, you can't do much better than O(n lg n), but you can do marginally better if you know something about your input.

这篇关于通用且实用的排序算法比O(n log n)更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！