多维快速排序算法

Question

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

为了处理多维排序，其中排序键是向量的，记录要重新排列，这样键的第一个组件是有序的，那么第一个分量相等的元素是按第二个组件排列的，依此类推。如果组件没有重复的kdeys，那么问题就归结为对第一个组件的排序；然而，在一个典型的应用程序中，每个组件可能只有几个不同的值和三个分区(移动到中间分区的下一个组件)。

我对上述案文的问题如下：

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

谢谢你的时间和帮助

Answer 1

作者描述了映射中键的辞典顺序。假设您有一对值的列表：

(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)之前。

当然，他们不一定是对的。您可以将字典顺序应用于具有任意数量值的元素。它们由第一组分、第二组分、第三组分等组成。

这个顺序的名称来自于我们如何在许多语言中排序单词。给出三个名字，约翰，吉姆和爱丽丝，我们怎么点？我们先按第一个字母订购，然后再按第二个字母订购，以此类推。这些名字的字典顺序是爱丽丝，吉姆，约翰。

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

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

按字典顺序排列这些字母的顺序是C, B, D, A。

Answer 2

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

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

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

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

Answer 3

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的第一个成分