algorithm - 查找快速排序中位数的中位数

Question

我正在使用中位数算法进行快速排序。我通常使用选择排序来获得 5 个元素的子数组的中位数。但是，如果有数千个子数组，则意味着我必须找到千位中位数的中位数。我想我不能使用选择排序来找到那个中位数，因为它不是最优的。

问题：

谁能建议我找到中位数的更好方法？提前致谢。

Answer 1

中位数算法无法通过找到每个大小为 5 的块的中位数然后对它们运行排序算法来找到中位数来工作。相反，您通常会对每个块进行排序，取每个块的中值，然后在这些中值上递归调用中值中值算法以获得良好的枢轴。在快速排序中使用中位数算法是非常罕见的，因为中位数算法的 O(n) 运行时间中的常数因子非常大，以至于它往往会显着降低性能。

对于这种原始方法，您可以尝试几种可能的改进。获得良好枢轴的最简单方法就是选择一个随机元素 - 这会导致 Θ(n log n) 运行时的概率非常高。如果您不习惯使用随机性，您可以尝试使用introselect 算法，它是对中位数算法的修改，它试图通过猜测一个可能是良好枢轴的元素并切断如果找到一个，则尽早递归。您也可以尝试编写 introsort，它使用快速排序并在算法出现退化时切换到不同的算法（通常是堆排序）。

希望这可以帮助！