为什么要比较各种麻烦？ [英] Why bother with comparison sorts?

问题描述

Introsort（通过扩展快速排序）占据最的真实世界的排序方法，红宝石，Python和STL之类的许多实现（）是常年算法的所有实例。理性情况下作出这些被使用，因为它们已被证明是最高效的，稳定的，多用途的排序中使用的算法。这在我看来，我们可以设想在电脑上整理（现实）的所有对象都是可数枚举。数字，字符，字符串，即使功能（至少在应用效果），适合进行非比较排序法（顺便说一句，如果你对字符串排序的疑惑，检查的美国国旗排序字符串与基数排序按字典序进行审查）。

Introsort (by extension quicksort) dominates most "real world" sorting methods, Ruby, Python, and many implementations of STL sort() are all instances of the perennial algorithm. A rational case is made that these are used as they have been shown to be the most performant, stable, multipurpose sorting algorithms in use. It seems to me that all objects that we could conceive of sorting (realistically) on a computer are countably enumerable. Numbers, characters, strings, even functions (at least results upon application) are amenable to a non-comparison sorting method (As an aside, if you have doubts about string sorting, examine American Flag Sort for a review of lexicographical ordering of strings with Radix sort).

有关物品分拣未标记的权重的情况下，我们必须使用比较排序鉴于没有标签。但是，我很难想出一个务实的情况下，这个属性保存（该属性是缺乏认知的，可订购标签），需要选一台机器上，从自然排序，以字典序。

For situations like sorting unlabeled weights, we must use a comparison sort given the absence of a label. However, I have difficulty coming up with a pragmatic case where this property holds (that property being the absence of a cognizable, orderable label) that requires sorting on a machine, ranging from natural orderings to lexicographical ordering.

候选人反为基数排序。基数排序不是基于比较。在一般情况下会表现比为O（n *日志（n））的速度更快，大幅了复杂性为O（K * N）跳动的n * log（n）的理论比较排序的限制，在许多情况下 - K是所需要的重新present特定项的比特数。

A candidate counterexample is Radix sort. Radix sort is not comparison based. In general it will behave faster than O(n*log(n)), beating the theoretical comparison sort limit of n * log(n) by a wide margin in many cases with a complexity of O(K*n) -- K being the number of bits that are required to represent a particular item.

关注像缓存失效和内存开销似乎是从实用主义的偏移赋予当代硬件的性能。关于内存开销快速排序（特别是今天）并不重要，因为你可以选择桶的数量来使用，所需的内存肯定会小于说，堆或归并的要求。

Concerns like cache invalidation and memory overhead seem to be an excursion from pragmatism given the properties of contemporary hardware. Memory overhead in relation to quicksort (particular today) is not critical, since you can choose the number of buckets to use and the required memory will certainly be less than say, heap or mergesort's requirements.

不过，我不认为立场，即基数排序是更快（任何实际的指标），比快速排序被广泛接受工程师之间或计算机科学家，但它不是一个令人难以置信的位置。在我们当代的世界观，我们一般接受Introsort作为对分拣效率的道路的尽头，并且在大多数情况下，我非常愿意接受。

However, I don't think the position that Radix sort is "faster" (for any practical metric) than Quicksort is widely accepted amongst Engineers or Computer scientists, but it's not an implausible position. In our contemporary worldview we generally accept Introsort as being the end of the road on sorting efficiency, and for the most part I am perfectly willing to accept that.

在另一方面，这是值得我们思考是否你的目标在直接的权利。

On the other hand, it's worth thinking whether you're aiming in the right directly.

简洁地说 - 为什么有比较排序都懒得

Succinctly stated -- Why bother with comparison sorts at all?

推荐答案

基数排序的速度取决于密钥的长度。如果你有长键如字符串，基数排序可能很慢。

The speed of radix sort depends on the length of the key. If you have long keys like strings, radix sort may be very slow.

此外，对于仅排序的几个项目的初始化成本可以由幅度outweight实际排序

Further, for sorting only a few items the initialization costs may outweight the actual sorting by a magnitude.

例如，如果您排序32位整数通过使用8位的基数则需要初始化的256桶至少4倍的名单 - 如果你只有20个左右的项目进行排序这和80互换将远远慢比约〜200比较/交换一个快速排序的需求。

For instance if you sort 32 bit integers by using a 8 bit radix you need to initialize at least 4 times the list of 256 buckets - if you only have 20 or so items to sort this and the 80 swaps will be far slower than the about ~200 comparisons/swaps a quicksort needs.

如果你长，像串排序什么，你有最长的字符串的每个字符水桶初始化 - 这可能会更糟

If you sort anything longer, like strings, you have for each character of the longest string a bucket initialization - this may be even worse.

这篇关于为什么要比较各种麻烦？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！