arrays - 快速排序枢轴

Question

使用快速排序对以下数组 a 进行排序，

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

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

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

我了解如何使用快速排序对数组进行排序，但是我不确定如何计算枢轴。

枢轴是否由 6 + 7 = 13 计算得出然后 13 / 2 = 6.5 (向下取整是 6 )所以枢轴是 2 (即第 6 个元素)？

我知道小于枢轴的元素出现在左侧，大于枢轴的元素出现在右侧，分区重复这个对子数组进行排序的步骤。

任何帮助将不胜感激。

Answer 1

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

The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot

因此三个选择:

第一个元素

中间元素

第一、中间和最后的中位数。

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

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