QuickSort中的媒體3分區

Question

我試圖理解快速排序與3中間分區。在找到數組中的第一個，中間和最後一個元素的中位數之後，通常的做法是將數組中的第二個元素（第n-1個索引）中值換位。我們這樣做是否有特定的原因？

Answer 1

原因是該算法不僅找到中位數，還排序低，中，高元素。在三種排列後，你知道[中] < = a [高]。所以你只需要在高點之前劃分元素，因爲[high]大於或等於pivot。

我們來看一個例子：low = 0，middle = 4，high = 8。您的陣列是這樣的：

lowerOrEqualToPivot XXX樞軸XXX greaterOrEqualToPivot

如果交換中間高，則需要括號之間分隔的8個元素：

[lowerOrEqualToPivot XXX greaterOrEqualToPivot XXX]樞軸

如果您將中間值與高位-1交換，則需要分割僅7個元素：

[lowerOrEqualToPivot XXXXXX] pivot greaterOrEqualToPivot

順便說一句，在第一行有一個錯誤：

int middle =（low + high）/ 2; //錯誤 int middle =（low + high）>>> 1; //正確

原因是，如果（低+高）大於Integer.MAX_VALUE，您將發生溢出，中間將爲負數。第二行總是會給你一個積極的結果。