c - 如何找到集合中第 i 个最大的数，并对第 i 个最大的数排序

Question

从 “Cormen Leiserson Rivest Stein，第 3 版，问题 9-1，点 C，第 224 页”，我有以下作业:

Given a set (array) A of n numbers, use an order-statistic algorithm to find the i-th largest number, partition around that number, and sort the i largest numbers.

我使用 Randomized-Select 算法(来自同一本书，第 216 页 - 它使用 Randomized-Partition 算法)找到第 i 个最小数，而我想找到第 i 个最大数(我们称它为“第 k 个”以避免混淆)。基本上，我可以获得第 k 个最大的数字:

n - ith + 1

然后我调用 RandomizedSelect() 来找到第 k 个最大的数字，一切都很好!

这里有一个例子(在 C 中)，说明我如何找到第 4 个最大的数字:

int A[10] = {3, 20, 15, 4, 1, 9, 18, 64, 22, 5}; // the given A set
int ith = 4; // I want to find the 4-th largest number of A
int kth = 10 - ith + 1; // I do this "conversion" for the reasons I explained above
int i = RandomizedSelect(A, 0, 9, kth); // it returns the index of A pointing to the 4-th largest number

printf("A vector: ");
for (j = 0; j < 10; j++) printf ("%u ", A[j]); // prints the A vector partially "ordered"

printf("\n4-th largest number: %u", A[i]); // prints the 4-th largest number

这里有一个输出示例:

A vector: 3 1 4 5 9 15 18 64 22 20

4-th largest number: 18

现在我不仅要第 4 个最大的数字，还要按顺序排列其他 4 个最大的数字(来自示例:18 20 22 64)。所以我只是在 A vector 上运行例如 MergeSort()，从之前找到的第 i 个索引开始直到结束。输出将为:18 20 22 64。

问题是作业说我必须围绕第 i (4) 个最大数字进行分区，并对其他 i (4) 个最大数字进行排序，然后运行 ​​MergeSort()，如前所述。但我不明白我为什么要那样做......在我的例子中，大约 18 分区没有任何意义，因为我试过并且这是我进行分区后 A vector 的输出(调用 SelectedPartition()):

3 1 4 5 9 15 18 64 22 20

18

...这是相同的输出!

那么，我对作业有什么误解？或者，我是否以更好的方式做到了？

Answer 1

有许多不同的算法可用于计算订单统计信息。许多算法，如 quickselect 或 median-of-medians 算法，会自动围绕第 k 个元素对数组进行分区，作为其实现的一部分。但是，不能保证选择算法必须这样做。例如，您可以通过将所有元素放入订单统计树数据结构中，然后查询第 k 个元素来实现选择。因此，放入显式分区步骤以确保分区发生是最正确的。

在您的情况下，由于您使用的算法已经进行了分区，因此您可以安全地忽略此步骤。

希望这对您有所帮助!