用二元trie对整数进行排序？

Question

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

1. 将每个整数插入二进制trie(trie,其中每个节点有两个子节点,一个标记为0,另一个标记为1).
2. 使用标准算法按排序顺序列出特里结构中的所有单词,按排序顺序列出所有整数.

这种排序算法是否曾在实践中使用过？

Answer 1

我以前从未见过这种算法.这可能是因为巨大的内存开销 - 每个数字都被炸成一个包含两个指针和一些自己的节点.在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 0递归排序所有数字并将其打印出来,然后递归排序以MSB 1开头的所有数字并打印出来.这个递归过程将继续,直到最终你完成了所有数字的位数,此时你只需要打印出每个数字.

上面的过程几乎完全相同的二进制快速排序算法,其工作方式如下:

• 如果没有数字,则什么也不做.
• 如果剩下一个号码,请将其打印出来.
• 除此以外:
  • 根据第一位将数字拆分为两组.
  • 递归排序并打印以0开头的数字.
  • Recurisvely排序并打印从1开始的数字.

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

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

希望这可以帮助!