快速排序透视 [英] Quicksort Pivot

问题描述

排序如下数组使用快速排序，

Sort the following array a using quicksort,

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

枢轴应该选择作为第一和最后一个元素，即的算术平均值（一个[0] + A [尺寸 - 1]）/ 2（四舍五入）。

显示如分区的算法的重要步骤和递归调用。

Show all important steps such as partitioning and the recursive calls to the algorithm.

我知道如何数组使用快速排序排序，但我不知道如何计算支点。

I understand how to sort the array using quicksort, however I'm not sure how to calculate the pivot.

是 6 + 7 = 13 然后 13/2 = 6.5 （向下取整为<计算支点code> 6 ），所以枢轴是 2 （即第六元素）？

Is the pivot calculated by 6 + 7 = 13 then 13 / 2 = 6.5 (rounded down is 6) so the pivot is 2 (i.e. the 6th element)?

我知道小于枢轴元素出现在左手侧，和元素比枢轴大于出现在右手侧，并且该分区重复排序的子阵列的这一步。

I know the elements less than pivot appear on the left hand side, and elements greater than the pivot appear on the right hand side, and the partition repeats this step of sorting the sub-array.

任何帮助将大大AP preciated。

Any help would be greatly appreciated.

推荐答案

有关快速排序，枢轴可以是你想要的任何元素。
请查看维基百科。

For quicksort, the pivot can be whatever element you want. Check out 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

三种选择这样的：

• 第一个元素


• 中东元素


• 第一，中间和最后的中位数。

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

And in you case using the mean of first and last element value would give you :

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

这篇关于快速排序透视的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！