algorithm - 所有类别的线性时间排序

Question

我有这个也许愚蠢的想法

因为我们有线性时间排序算法，用于使用计数排序、基数排序的整数等受限类别。

就像在计算机中一样，所有类别的数字类型最终都以字节序列编码（在某种程度上与整数等类似）。是否能够说明我们可以使用那些线性时间排序算法对所有这些数字进行线性时间排序？

Answer 1

当然，虽然细节因类型而异。一个简单的例子是 IEEE-754 浮点值（32 位和 64 位），它几乎可以像整数一样进行排序。（更具体地说，它们可以像符号大小整数一样进行排序。）所以基数排序可以正常工作。

对于字符串，当您有太多的字符串无法放入内存时，一种不常见的技术是按前缀“分箱”它们，这是一种基数排序。

对于短位域值（如整数或如上所述的浮点数），从左到右的一次位基数排序实际上只是快速排序的一种变体，因为它基本上只是一种找到一个合理的支点。与快速排序不同，它保证了有限的递归深度（在 32 位值的情况下为 32）。另一方面，快速排序通常具有更小的递归深度，因为数据集大小的log _{2通常远小于 32。}

快速排序的主要优点是您可以编写算法（STL 风格），而不需要对被排序的数据类型一无所知，除了如何调用函数来比较两个值。基数排序不能这样说。制作通用版本要困难得多。

编辑添加了一个重点：

过分强调 O(n) 和 O(n log n) 之间的差异是很常见的。对于非常大的 n，它们是不同的。但是对于大多数现实世界的非谷歌大小的问题，log n 是一个小整数。当有一个需要 2n log ₂ n 秒的 O(n log n) 算法时，使用需要 100n 秒的 O(n) 算法是没有意义的，除非 log n 大于 50，也就是说n 大于 1,125,899,906,842,624。

Answer 2

你不能。如果您有一段由以下字节表示的数据：

11001100 00110011
(204)    (51)

如果您要使用基数排序之类的方法对它们进行排序，您将得到：

00110011 11001100
(51)     (204)

唯一的问题是，这不再是您写入磁盘的数据，而是完全不同的数据，甚至可能根本没有任何意义（垃圾）。