1

我正在阅读 C++ RobertSedwick 的算法中的多维排序，如下所示。

为了处理多维排序，其中排序键是向量，并且要重新排列记录，以便键的第一个分量是有序的，然后第一个分量相等的那些按第二个分量排序，依此类推。如果组件没有重复的 kdey，则问题归结为对第一个组件进行排序；然而，在典型应用中，每个组件可能只有几个不同的值，并且是三向分区（移动到中间分区的下一个组件。

我对上述文字的问题是

  1. 作者所说的第一部分，第二部分是什么意思？
  2. 如果组件没有重复的键，那么作者的意思是什么问题减少到对第一个组件进行排序？

感谢您的时间和帮助

4

3 回答 3

2

作者正在描述映射中键的字典顺序。想象一下，您有一个值对列表：

(4 3), (2 3), (1 4), (4 2)

每对中的第一个被称为“第一个组件”，第二个当然是“第二个组件”。这些项目的字典顺序是：

(1 4), (2 3), (4 2), (4 3)

我们如何做到这一点？首先，这些对按它们的第一个组件排序。第一个组件是4, 2, 1, 4按顺序排列的1, 2, 4, 4。但是有两个四。我们可以通过它们的第二个组件进一步排序它们，例如(4 2)之前(4 3)的。

当然，它们不必成对。您可以将字典顺序应用于具有任意数量值的元素。它们按第一个组件排序，然后是第二个，然后是第三个，依此类推。

这种排序的名称来自我们如何对多种语言中的单词进行排序。给定三个名字，约翰、吉姆和爱丽丝，我们如何为它们排序？首先我们按第一个字母排序，然后是第二个字母，依此类推。这些名字的字典顺序是 Alice、Jim、John。

在作者的描述中，这种排序被用于对地图的键进行排序。也就是说，这些对被映射到某个值。例如，键可以是一对，值是一个字母：

(4 3) => A, (2 3) => B, (1 4) => C, (4 2) => D

在按字典顺序对键进行排序后，这些字母的顺序将是C, B, D, A.

于 2012-11-27T13:58:19.560 回答
1

1-如果您有例如 3 件物品：

A: {1 2 3 4 5}
B: {2 5 5 5 5}
C: {2 6 6 6 6}

A 的第一个分量是 1，B 和 C 是 2

2-如果您必须对 A 和 B 进行排序，因为 A 的第一个组件 < B 的第一个组件，您不必再进一步，也不必像您那样比较第二个元素做比较 B 和 C

于 2012-11-27T14:02:14.947 回答
1

作者所说的第一部分，第二部分是什么意思？

数组中的第一个、第二个元素。这是： int arr1[] = {1,2,3,4}, arr2[] = {5,6,7,8} arr1 的第一个分量是 1，arr2 的第一个分量是 5。

如果组件没有重复的键，那么作者的意思是什么问题减少到对第一个组件进行排序？

如果数组中的所有第一个元素都不同，则只需对第一个元素进行排序。

于 2012-11-27T13:58:50.823 回答