线性时间分类法为所有类别 [英] linear time sortings for all categories

问题描述

我有这个，也许愚蠢的想法

I had this maybe stupid thought

因为我们有线性时间使用计数排序排序算法进行约束categroies喜欢整数，基数排序。

since we have linear time sorting algorithms for constrained categroies like integers using counting sort, radix sort.

在电脑的话，所有类别的号码类型终于EN codeD中的字节序列（这是与整数等等类似某种程度）。是不是能够说我们可以做线性时间使用这些线性时间排序算法排序的所有这些数字？

as in computer word, all categories of number types are finally encoded in byte sequences (which are to some extent similar with integers etc... ). is it able to state that we can do linear time sorting for all these numbers using those linear time sorting algorithms ?

推荐答案

当然，虽然细节各不相同类型的输入。一个简单的例子是IEEE-754浮点数的值（32位和64位），这几乎可以被排序，就像它们是整数。 （更具体地，它们可以被分类，就像它们是符号大小的整数。）因此，一个基数为排序将很好地工作。

Sure, although details vary from type to type. One simple example is IEEE-754 floating point values (both 32-bit and 64-bit), which can almost be sorted as though they were integers. (More specifically, they can be sorted as though they were sign-magnitude integers.) So a radix-sort would work fine.

有关的字符串，一当你有太多的人，以适应在内存中未少见的技术是斌他们由preFIX，这是一个不同的基数排序。

For character strings, a not-uncommon technique when you have too many of them to fit in memory is to "bin" them by prefix, which is a variety of radix-sort.

有关短位字段值（像整数或，如上所述，浮点数），一个左到右位在一次一基数排序是真的快速排序只是一个变型中，因为它基本上只办法找到一个合理的支点。不像快速排序，它保证一个有限递归深度（32的32位值的情况下）。另一方面，快速排序通常具有小得多的递归深度，因为log <子>的数据集大小的2 通常大于32少很多。

For short bit-field values (like integers or, as above, floating point numbers), a left-to-right bit-at-a-time radix sort is really just a variant of quicksort, since it is basically just a way to find a plausible pivot. Unlike quicksort, it guarantees a finite recursion depth (32 in the case of 32-bit values). On the other hand, quicksort usually has a much smaller recursion depth, since log₂ of the dataset size is usually a lot less than 32.

快速排序的主要好处是，你可以写算法（STL风格）在不知道数据类型进行排序在所有的，不是如何调用一个函数来比较两个值的其他任何东西。的基数排序同样不能说;它的很多困难，使一个仿制版本。

The main advantage of quicksort is that you can write the algorithm (STL style) without knowing anything about the datatype being sorted at all, other than how to call a function to compare two values. The same cannot be said of radix-sort; it's a lot harder to make a generic version.

编辑补充很重要的一点：

Edited to add one important point:

这是很常见过分强调为O（n）和O之间的差异（N log n）的。对于的非常大的n 的，它们是不同的。但是对于大多数现实世界的非谷歌规模的问题，日志n是小的整数。这是没有意义的使用O（n）的算法，取​​100N秒时，有一个为O（n log n）的算法，采用2N日志 ₂ n秒，除非为log N均大于50，这是说是n均大于1,125,899,906,842,624

It's very common to overemphasize the difference between O(n) and O(n log n). For very large n, they are different. But for most real-world non-Google-sized problems, log n is a small integer. It wouldn't make sense to use an O(n) algorithm which takes 100n seconds when there is an O(n log n) algorithm which takes 2n log₂ n seconds, unless log n were greater than 50, which is to say that n were greater than 1,125,899,906,842,624.

这篇关于线性时间分类法为所有类别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！