Quicksort Pivot

Question

使用quicksort对以下数组进行排序,

[6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

应选择枢轴作为第一个和最后一个元素的算术平均值,即(a[0] + a[size - 1]) / 2 (rounded down).

显示所有重要步骤,例如分区和对算法的递归调用.

---

我理解如何使用quicksort对数组进行排序,但是我不知道如何计算数据.

被枢轴通过计算6 + 7 = 13则13 / 2 = 6.5(向下取整的6),因此枢轴2(即6元)？

我知道小于枢轴的元素出现在左侧,并且大于枢轴的元素出现在右侧,并且分区重复这个对子阵列进行排序的步骤.

任何帮助将不胜感激.

Answer 1

对于快速排序，枢轴可以是您想要的任何元素。查阅Wikipedia。

通过为枢轴选择随机索引，选择分区的中间索引或（特别是对于较长的分区）选择枢轴的分区的第一个，中间和最后一个元素的中位数，可以轻松解决此问题。

因此，三个选择：

• 第一要素
• 中间元素
• 第一，中间和最后一个的中位数。

在您的情况下，使用第一个元素值和最后一个元素值的平均值会给您：

6 + 7 = 13
13 / 2 = 6.5
6.5 rounded down = 6

Answer 2

对于给定的数组[6, 11, 4, 9, 8, 2, 5, 8, 13, 7]

计算如下：

• 选择第一个元素是6

• 选择列表的最后一个元素7

• 选择中间元素mid = (length%2==0) ? (length/2)-1 : (length-1)/2，即8

• 这将创建一个数组并对其进行排序[6,7,8]，现在数组中的中间元素是中位数。