Quicksort Pivot

| 使用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个元素）吗？我知道小于枢轴的元素出现在左侧，大于枢轴的元素出现在右侧，并且分区重复了对子数组进行排序的步骤。任何帮助将不胜感激。

已邀请:

4 个回复

播匣扦阔食

对于快速排序，枢轴可以是您想要的任何元素。查阅Wikipedia。通过为枢轴选择随机索引，选择分区的中间索引或（特别是对于较长的分区）选择枢轴的分区的第一个，中间和最后一个元素的中位数，可以轻松解决此问题。因此，三个选择：第一要素中间元素第一，中间和最后一个的中位数。在您的情况下，使用第一个元素值和最后一个元素值的平均值会给您：

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

佬棠

顺带提一下问题的措辞，枢轴应该只是6，而不必是数组中的第6个项目。绝对是这种情况，因为例如，如果数组中只有3个项目，并且算术平均值大于3，则您将没有选择枢轴的选择，因为没有任何项目具有该索引。注意：注意在数组中索引元素的方式。您说第6个元素是\'2 \'，如果您的编程语言将索引从0开始则可能是\'5 \'。

超可林

您的枢轴是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))

蓄荣糖些

该计算中枢轴的位置并不重要，quicksort根据元素是否大于枢轴对元素进行排序。然后，将枢轴放置在两组之间（越来越少）。

要回复问题请先登录或注册

Quicksort Pivot

4 个回复

发起人

arrays

sorting

pivot

quicksort

问题状态

Quicksort Pivot

与内容相关的链接

4 个回复

发起人

arrays

sorting

pivot

quicksort

问题状态