algorithm - 多维快速排序算法

Question

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

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

我对以上文字的问题是

1. 作者所说的第一个组件、第二个组件是什么意思？
2. 作者所说的如果组件没有重复键，问题会简化为对第一个组件进行排序是什么意思？

感谢您的时间和帮助

Answer 1

作者在描述lexicographical order映射中的键。假设您有一个值对列表:

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

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

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

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

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

按字典顺序对键进行排序后，这些字母的顺序为 C, B, D, A。