arrays - 你能在快速排序中选择你想要的任何主元吗？

Question

我最近看到Quick Sort - Computerphile YouTube 上关于快速排序如何工作的视频(纸上)，我有一个问题。想象一下，我们有一个数组，其中包含例如 "27,6,19,2,15,9,10" 。首先我选择10作为枢轴和数组变成这样: 9,2,6 |10| 27,19,15 。然后我选择6作为左侧未排序数组的枢轴，它变成 2 |6| 9对于正确的我选择 19作为主元，右侧未排序的数组变为 15 |19| 27 。问题是:我可以选择任何我想让我的工作变得更轻松的枢轴(就像我在这个例子中所做的那样)还是还有其他东西？

编辑:如果我选择 27 而不是 19 作为主元，数组会是什么样子？

Answer 1

您可以选择任何值，使分区的任何部分都不会为空，即不小于最小值也不大于最大值。 (该值不必是数组的元素之一。)

分区越平衡(越接近中位数)越好。尽管从未这样做过，但算术平均值可以做到。

常见的策略是三个元素的中位数(第一个元素、中心元素和最后一个元素)。