快速排序枢轴

排序下面阵列的使用快速排序，快速排序枢轴

[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（即，第六元件）？

我知道左侧显示的元素少于枢轴，右侧显示大于枢轴的元素，分区将重复此步骤对子数组进行排序。

任何帮助将不胜感激。

来源

2011-05-24 Paradox

对于快速排序，枢轴可以是任何你想要的元素。结账Wikipedia。

的问题很容易通过选择任一一个随机索引用于枢轴，选择选择位数的中间索引的分区的或（特别是对于较长的分区）解决了第一，中间和最后分区用于枢轴的元件从而

三种选择：

网络连接第一个元素
中间元素
第一个，中间和最后一个的中间值。

而且在使用第一和最后一个元素的意思是你的情况下值会给你：

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

来源

2011-05-24 14:19:56

谢谢老兄，非常感谢您的明确帮助。 – Paradox 2011-05-24 14:32:06

顺便说一句，问题的措辞，枢轴应该只是6，不一定是数组中的第6项。

这是最明显的例子，因为如果在数组中只有3个项目，例如算术平均值大于3，那么您将没有选择的主点，因为没有该项目指数。

注意：小心你索引数组中的元素的方式。你说第6个元素是'2'，如果你的编程语言开始索引为0，那么它可能是'5'。

来源

2011-05-24 14:17:18 PaulV

你的支点是6.你的支点不是第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))

来源

2011-05-24 14:17:28 djfoxmccloud

从计算枢轴的位置并不重要，快速排序排序基于元素无论它们是否多于或少于枢轴。然后将枢轴放置在两组之间（或多或少）。

来源

2015-09-04 06:45:51 txsaw1

快速排序枢轴

回答

相关问题