algorithm - 用二进制树对整数进行排序？

Question

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

1. 将每个整数插入 binary trie (每个节点都有两个子节点的 trie，一个标记为 0，一个标记为 1)。
2. 使用standard algorithm for listing all words in a trie in sorted order , 按排序顺序列出所有整数。

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

Answer 1

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

但是，该算法与most-significant digit radix sort 极其密切相关(也称为 二元快速排序)，在实践中经常使用。事实上，您可以将二元快速排序视为该算法的一种节省空间的实现。

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

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

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

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

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

• 如果没有剩余数字，什么也不做。
• 如果还剩一个数字，打印出来。
• 否则:
  • 根据第一位将数字分成两组。
  • 递归排序并打印从 0 开始的数字。
  • 递归排序并打印从 1 开始的数字。

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

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

希望这对您有所帮助!