arrays - Pivots in quicksort : does it have to be an array element?

Question

I'm a physicist, please excuse my ignorance :(

Does the pivot have to be an array element? If so, why? Does choosing an array element as pivot offer any considerable advantage?

I ask this because choosing the average of the array elements seems like it would be fairly robust (avoid cases where the subarrays are 1 and N-1 long etc). The average might not be an array element (eg: it could be a float for an array of integers)

Thanks!

Answer 1

您可以非常轻松地实现一个快速排序版本，它不需要枢轴是数组的实际元素。该算法可以通过一些简单的修改正常工作。但是您必须自己编写代码：标准快速排序确实要求枢轴是数组的一个元素。

不过，我不确定这样做有什么好处。首先，不能保证平均值是一个好的支点。此外，由于这需要遍历整个数组，并且在递归调用期间也会发生这种情况，因此它可能会减慢算法的速度，以克服优越的枢轴选择带来的任何优势。

获得良好支点的一个非常好的策略是选择一个小的随机样本（比如 10 个元素），然后选择这个样本的中位数。