3个分区中位数 [英] Median of 3 partitioning

问题描述

我发现下面的code查找支点使用快速排序第一，最后和中间元素的值：

I found the following code for finding a pivot for quicksort using median of first, last and middle element:

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做高，而不是交换？

I want to know after finding the median, why is the swap done with index high-1 instead of high?

推荐答案

的原因是，该算法不仅找到了中间值，这也排序低，中，高的元素。三排列之后，你知道，[中] LT = A（高）。所以，你只需要分区前高的元素，因为[大]大于或等于支点。

The reason is that the algorithm does not only find the median, it also sorts the low, middle and high elements. After the three permutations you know that a[middle]<=a[high]. So you need only to partition the elements before high, because a[high] is greater or equal to pivot.

让我们来看一个例子：低= 0，中间= 4，高= 8。你的阵列是这样的：

Let's look at an example: low=0, middle=4 and high=8. Your array is like this:

lowerOrEqualToPivot X X X pivot X X X greaterOrEqualToPivot

如果您交换中间高，你需要进行分区括号中的8个元素：

If you swap middle with high, you need to partition the 8 elements between brackets :

[ lowerOrEqualToPivot X X X greaterOrEqualToPivot X X X ] pivot

如果您交换中间用高1，您需要拆分仅7个元素：

If you swap middle with high-1, you need to split only 7 elements:

[ lowerOrEqualToPivot X X X X X X ] pivot greaterOrEqualToPivot

通过有在第一线中的错误的方法：

By the way there is a bug in the first line:

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

的原因是，如果（低+高）大于Integer.MAX_VALUE更大你将有一个溢流和中间将是一个负数。第二行总会给你一个积极的结果。

The reason is that if (low + high) is greater than Integer.MAX_VALUE you will have an overflow and middle will be a negative number. The second line will always give you a positive result.

这篇关于3个分区中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！