java - 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？

最佳答案

原因是该算法不仅能找到中值，而且能对低、中、高元素进行排序。经过三次排列，你知道a[中间]让我们看一个例子：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

如果用high-1替换middle，则只需要拆分7个元素：

[ lowerOrEqualToPivot X X X X X X ] pivot greaterOrEqualToPivot

顺便说一下，第一行有个bug：

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

原因是，如果（low+high）大于integer.max_值，则会出现溢出，而middle为负数。第二行总是给你一个积极的结果。

关于java - 3个分区的中位数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13144484/