3

我找到了以下代码，用于使用第一个、最后一个和中间元素的中值查找快速排序的枢轴：

int middle = ( low + high ) / 2;
if( a[ middle ].compareTo( a[ low ] ) < 0 )
    swapReferences( a, low, middle );
if( a[ high ].compareTo( a[ low ] ) < 0 )
    swapReferences( a, low, high );
if( a[ high ].compareTo( a[ middle ] ) < 0 )
    swapReferences( a, middle, high );

// Place pivot at position high - 1
swapReferences( a, middle, high - 1 );
Comparable pivot = a[ high - 1 ];

我想知道找到中位数后，为什么交换是用索引 high-1 而不是 high 完成的？

4

1 回答 1

1

原因是该算法不仅找到中位数，还对低、中、高元素进行排序。在三个排列之后，您知道 a[middle]<=a[high]。所以只需要对high之前的元素进行分区，因为a[high]大于等于pivot。

让我们看一个例子：low=0，middle=4，high=8。你的数组是这样的：

lowerOrEqualToPivot X X X pivot X X X greaterOrEqualToPivot

如果将中间与高交换，则需要在括号之间划分 8 个元素：

[ lowerOrEqualToPivot X X X greaterOrEqualToPivot X X X ] pivot

如果将 middle 与 high-1 交换，则只需要拆分 7 个元素：

[ lowerOrEqualToPivot X X X X X X ] pivot greaterOrEqualToPivot

顺便说一句，第一行有一个错误：

int middle = ( low + high ) / 2; //Wrong
int middle = ( low + high ) >>> 1; //Correct

原因是如果 (low + high) 大于 Integer.MAX_VALUE 您将有溢出，而中间将是一个负数。第二行总是会给你一个积极的结果。

于 2013-01-19T14:10:35.287 回答