快速排序中的枢轴元素

Question

使用快速排序算法对以下数组 a 进行排序：

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

应该选择第一个元素和最后一个元素的算术平均值作为枢轴，即 (a[0] + a[size - 1]) / 2（向下取整）。

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

---

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

枢轴是通过 6 + 7 = 13 然后 13 / 2 = 6.5（向下取整为 6），所以枢轴是 2（即第6个元素）吗？

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

任何帮助都将不胜感激。

- Paradox

Answer 1

对于快速排序，枢轴可以是任何元素。请查看维基百科。解决问题的方法是选择随机索引作为枢轴，选择分区的中间索引或（特别是对于更长的分区）选择分区的第一个、中间和最后一个元素的中位数作为枢轴。因此有三个选择：

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

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

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

- i.am.michiel

---

我认为这是错误的，但错误在原始问题中。你纠正了它们，然后进行了他们要求的错误计算，当你取平均值（第一个，最后一个）。你想要的是（第一个，中间，最后一个）的中位数。虽然关于教练错过了选择枢轴点的更好策略之一（随机），这是一个好观点。 - Kenny Ostrom

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]，此时其中位数为中位数。

- Rupesh

---

哇，这是一个8年前的问题，直到现在都没有好的答案。我投了一票，但你的解释相当简洁。 - Kenny Ostrom

Answer 3

顺便提一下，问题的措辞应该只是6，而不一定是数组中的第6个项目。

这绝对是这种情况，因为如果数组中只有3个项，例如，算术平均值大于3，那么您将没有枢轴可供选择，因为没有具有该索引的项目。

注意：小心数组中元素的索引方式。您说第6个元素是“2”，但如果您的编程语言从0开始索引，则可能是“5”。

- PaulV

Answer 4

您的枢轴是6。 您的枢轴不是第六个元素 现在，您可以应用以下算法。

function quicksort(array)
 var list less, greater
 if length(array) ≤ 1
     return array  // an array of zero or one elements is already sorted
 select and remove a pivot value pivot from array
 for each x in array
     if x ≤ pivot then append x to less
     else append x to greater
 return concatenate(quicksort(less), pivot, quicksort(greater))

- djfoxmccloud

Answer 5

从那个计算中得出的枢轴位置并不重要，快速排序是根据元素是否大于或小于枢轴来对它们进行排序。然后将枢轴放置在两个集合（更多和更少）之间。

- txsaw1

---

枢轴元素是否可能不在数组中？ - piepi