algorithm - 无痕就地选择排序

Question

给定一个长度为 n 的数组 A[1..n]，每个单元格包含一个〈height,weight〉对。所有身高值都是不同的，所有体重值也是如此。该数组按高度值的升序排序。您的任务是设计一个递归分治算法，给定一个整数 k∈[1,n]，找到具有第 k 个最小权重值的条目。在每个递归级别中，您只能使用 O(1) 额外空间。尽管您的算法可以在需要时重新排序 A 的条目，但它必须在终止之前恢复条目的原始顺序。您的算法必须在 Θ(n) 时间内运行。

我能想到的算法是选择排序，但我无法在时间和空间复杂度要求的情况下做到这一点。任何帮助或方向将不胜感激。

标签： algorithmsortingtime-complexitydivide-and-conquerselection-sort

Answer 1

如果算法平均为 O(n)，则可以使用快速排序。快速排序可以平均在 O(n) 中找到第 k 个元素，直到证明枢轴被证明是第 k 个元素本身（O(n^2) 最坏情况和 O(n) 平均）。

现在棘手的部分：您需要恢复原始数组。对排序数组的分区过程的第一次迭代很简单：只需以相反的方向运行该过程并重建初始数组。现在递归的想法出现了：如果枢轴恰好大于第k个元素，你仍然有左子数组排序：你可以重复这个过程，找到第k个并恢复数组。但是，如果您发现枢轴低于第 k 个元素......然后恢复数组并运行快速排序“反射”（您开始从右到左移动）。在这种情况下，来自枢轴的右子数组将被排序。递归地重复过程。