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 ];

中央値を見つけた後に知りたいのですが、スワップが高ではなく高-1 で行われるのはなぜですか?

4

1 に答える 1

1

その理由は、アルゴリズムが中央値を見つけるだけでなく、低、中、高の要素もソートするためです。3 つの順列の後、a[middle]<=a[high] であることがわかります。したがって、a[high] はピボット以上であるため、high の前に要素を分割するだけで済みます。

例を見てみましょう: 低 = 0、中 = 4、高 = 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 より大きい場合、オーバーフローが発生し、中間が負の数になるためです。2 行目は常に肯定的な結果をもたらします。

于 2013-01-19T14:10:35.287 に答える