algorithm - 在 QuickSort 中选择一个枢轴

Question

我正在阅读有关 QuickSort 的文章，看起来理想情况下，他们使用随机算法来选择至少有 25-75 个数组拆分的主元。 为什么他们不能计算数组的中值并在每次递归调用中选择最接近中值的值？

我认为它会花费相同的运行时间，甚至可能比随机方法更好。

Answer 1

使用中位数的中位数，可以选择接近中位数，但开销很大，有效地对 5 组进行排序。Wiki 文章:

https://en.wikipedia.org/wiki/Median_of_medians

请注意，中位数的中位数可以就地实现。

对于随机主元，计算随机索引的代码会在分区步骤中占用大量时间。

一种更简单的方法是使用 first、middle、last 的中位数，以避免已排序或反向排序数据的最坏情况时间，正如 yeputons 所回答的那样，使用切换到堆排序的 introsort(基于递归级别) 以避免最坏的情况发生。