为什么在快速排序算法中最优的选择是中间元素？

Question

最近我在brilliant.org上了一门课程，我正在探索一堂关于QuickSort算法的课，发现了一个问题。

以下哪一项将在快速排序的每一步提供最佳的枢轴选择？

• A.第一个位置的要素
• B.具有最小值的元素
• C.随机选择的元素
• D.要素的中位数

答案是"D“

但在现实生活中的数组中，上面的选项又是怎样的呢？

列出的理由是

“的中值，将允许算法将列表分割成大致相等的部分，因此运行时将加快速度。”

。

我们永远不知道一个元素的值，如果我们选择一个中间值，如何保证数组被分割成两个部分？据我们所知，它可能是最高的或最低的，或非常接近最高或最低的数字。这将使左数组或右数组几乎为空。

Answer 1

您似乎混淆了中值和中间元素。

未排序数组的中间元素实际上可能接近最低值或最高值。

另一方面，中位值是有一半值比较小，一半值比较大的值。

使用中间值作为快速排序中的枢轴的优点是，它保证两个分区尽可能接近相同大小。

使用中值值的问题是，您需要知道所有元素的值，才能知道中位数是哪个。这使得在实践中很难使用中值，尽管它是理论上的最优值。