6

由于每个整数都可以表示为一系列具有一定长度的位，因此您似乎可以按以下方式对一堆整数进行排序：

  1. 将每个整数插入二元树（每个节点有两个子节点的树，一个标记为 0，一个标记为 1）。
  2. 使用按排序顺序列出trie 中所有单词的标准算法，按排序顺序列出所有整数。

这种排序算法曾经在实践中使用过吗？

4

1 回答 1

6

我以前从未真正见过这种算法。这可能是因为巨大的内存开销 - 数字的每一位都被炸成一个包含两个指针和自己的一点的节点。在 32 位系统上，这是 64 倍的内存爆炸，而在 64 位系统上，这是 128 倍的内存爆炸。

但是，该算法与实际中经常使用的最高有效位基数排序（也称为二进制快速排序）密切相关。事实上，您可以将二进制快速排序视为该算法的一种节省空间的实现。

连接基于 trie 的递归结构。如果您考虑 trie 的顶部节点，它将如下所示：

           *
          / \
         /   \
    All #s  All #s
     with    with
    MSB 0   MSB 1

如果您要使用 trie 的标准前序遍历来按排序顺序输出所有数字，则该算法将首先按排序顺序打印出所有以 0 开头的数字，然后按排序顺序打印出所有以 1 开头的数字命令。（永远不会打印根节点，因为所有数字都具有相同的位数，因此所有数字实际上都存储在叶子上）。

因此，假设您想模拟构建 trie 并对其进行前序遍历的效果。您会知道这将从打印出所有带有 MSB 0 的数字开始，然后将打印出带有 MSB 1 的所有数字。因此，您可以通过将数字分成两组开始 - 一组所有数字都具有 MSB 0，一个所有数字都具有 MSB 1。然后，您将对所有具有 MSB 0 的数字进行递归排序并打印出来，然后对所有以 MSB 1 开头的数字进行递归排序并打印出来。这个递归过程会一直持续下去，直到你最终遍历了数字的所有位，此时你只需单独打印出每个数字。

上述过程几乎与二进制快速排序算法相同，其工作原理如下：

  • 如果没有数字，什么也不做。
  • 如果还剩一个号码，打印出来。
  • 除此以外：
    • 根据数字的第一位将数字分成两组。
    • 递归排序并打印从 0 开始的数字。
    • 递归排序并打印从 1 开始的数字。

这些算法之间存在一些差异。二进制快速排序通过递归地将列表分成越来越小的部分，直到所有内容都排序，而基于特里树的算法构建特里树，然后重建数字。但是，您可以将二进制快速排序视为算法的一种优化，它同时构建和遍历特里树。

简而言之：由于内存开销，我怀疑有人会想要使用基于 trie 的算法，但它确实为推导 MSD 基数排序算法提供了一个很好的起点！

希望这可以帮助！

于 2013-01-15T05:49:11.570 回答