由于每个整数都可以表示为一定长度的一系列位，因此似乎可以按以下方式对一组整数进行排序:
- 将每个整数插入到二叉树中(每个节点有两个子节点，一个标记为0，一个标记为1)。
- 使用标准算法按顺序列出所有单词在一个trie中，列出所有整数按顺序。
这个排序算法在实践中使用过吗?
我还没有见过这种算法被使用过。这可能是因为巨大的内存开销——数字的每一点都被扩展到一个包含两个指针和它自己的一点的节点。在32位系统上，这是内存的64倍膨胀，在64位系统上，这是内存的128倍膨胀。
然而，该算法与实践中经常使用的最高有效位数基数排序(也称为二进制快速排序)密切相关。实际上，您可以将二进制快速排序视为该算法的空间高效实现。
连接基于tree的递归结构。如果考虑树的顶部节点，它看起来像这样:
*
/
/
All #s All #s
with with
MSB 0 MSB 1
如果您要使用标准的预序遍历来按排序顺序输出所有的数字，算法将首先按排序顺序打印出所有以0开头的数字，然后按排序顺序打印出所有以1开头的数字。(根节点永远不会被打印出来，因为所有的数字都有相同的位数，因此所有的数字实际上都存储在叶子节点上)
假设您想模拟构建树并对其进行预序遍历的效果。您会知道，这将首先打印出MSB为0的所有数字，然后打印出MSB为1的所有数字。因此，您可以首先将数字分成两组——一组所有数字的MSB为0，另一组所有数字的MSB为1。然后对MSB为0的所有数字进行递归排序并打印出来，然后对MSB为1开头的所有数字进行递归排序并打印出来。这个递归过程会一直持续下去，直到你最终遍历了所有的数字位，这时你只需要单独打印出每个数字。
上面的过程几乎与二进制快速排序算法相同，其工作原理如下:
- 如果没有剩余号码，不做任何操作。
- 如果还剩一个数字，打印出来
- 否则:
- 根据数字的第一个位将数字分成两组
- 递归排序并打印以0开头的数字。
- 递归排序并打印以1开头的数字。
这些算法之间存在一些差异。二进制快速排序的工作原理是递归地将列表分成越来越小的部分，直到所有内容都排序，而基于尝试的算法则构建trie，然后重建数字。但是，您可以将二进制快速排序视为同时构建和遍历trie的算法的优化。
所以简而言之:由于内存开销，我怀疑有人会想要使用基于尝试的算法，但它确实为派生MSD基数排序算法提供了一个很好的起点!
希望这对你有帮助!