2

我想按所有元素对元组数组进行排序（就像它们在特里一样）。如果输入是 (1,2,5), (1,2,3), (1,1,4), (2,8,9)，对应的输出是 (1,1,4), ( 1,2,3), (1,2,5),(2,8,9)。相应的尝试将是：

    root
   /   \
  1     2
 / \    | 
1   2   8
|  /\   |
4 3  5  9

我正在考虑为元组中的每个位置使用搜索树。还有一种明显的幼稚方式（按第一个位置排序，然后按第二个位置排序，等等）。有人看到更好的方法吗？

4

3 回答 3

3

您在上面概述的基于 trie 的方法与对元组进行最重要的数字基数排序非常相似。您基本上是根据它们的第一个数字将它们分配到存储桶中，然后根据剩余的数字递归地将存储桶细分为更小的组。您可能需要考虑显式执行 MSD 基数排序而不是构建 trie，因为当数据稀疏时，尝试可能会导致内存效率低下，而 MSD 基数排序具有相当好的内存使用率（特别是如果您隐式实现所有内容）。

在您上面给出的示例中，元组中的所有数字都是个位数。如果是这种情况，您最多可以有 10 × 10 × 10 = 1000 个可能的不同元组，这不是很大。在这种情况下，您可能需要考虑仅使用带有自定义比较器的标准排序算法，因为更优化的排序的好处在这种规模下可能不会那么明显。另一方面，如果您的元组中有更多条目，那么可能值得投资于更聪明的排序，例如 MSD 基数排序。

希望这可以帮助！

于 2013-03-18T17:24:24.217 回答
1

基数排序到特里，就像合并排序到二叉树

于 2013-03-18T17:57:35.297 回答
0

如何保持简单，并将元组值视为元组的所有元素的总和到某个基数，比如 10，然后我们将 (1,2,5) 设为 125，所以不时地用任何简单的比较排序（如堆）对它们进行排序种类

于 2013-03-18T18:13:05.220 回答