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而不是高？

原因是该算法不仅找到中位数，还对低、中、高元素进行排序。经过三种排列后，您知道 a[middle]

让我们看一个例子：低=0，中=4，高=8。你的数组是这样的：

lowerOrEqualToPivot X X X pivot X X X greaterOrEqualToPivot

如果将 middle 与 high 交换，则需要将 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，则会发生溢出，并且 middle 将为负数。第二行总是会给你一个积极的结果。