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

Question

我有这个可能是愚蠢的想法

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

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

Answer 1

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

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

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

快速排序的主要优点是，除了如何调用函数来比较两个值之外，您可以在完全不知道被排序的数据类型的情况下编写算法(STL 风格)。基数排序不能这样说；制作通用版本要困难得多。

编辑添加一个要点:

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