quicksort - QuickSort 中的 Media-of-3 分区

Question

我试图用 3 分区中位数来理解快速排序。在找到数组中第一个、中间和最后一个元素的中值后，一种常见的做法是将中值与数组中倒数第二个元素（第 n-1 个索引）交换。我们这样做有什么特别的原因吗？

Answer 1

原因是该算法不仅找到中位数，还对低、中、高元素进行排序。在三个排列之后，您知道 a[middle]<=a[high]。所以只需要对high之前的元素进行分区，因为a[high]大于等于pivot。

让我们看一个例子：low=0，middle=4，high=8。你的数组是这样的：

lowerOrEqualToPivot XXX 枢轴 XXX GreaterOrEqualToPivot

如果将中间与高交换，则需要在括号之间划分 8 个元素：

[ lowerOrEqualToPivot XXX 更大OrEqualToPivot XXX ] 枢轴

如果将 middle 与 high-1 交换，则只需要拆分 7 个元素：

[ lowerOrEqualToPivot XXXXXX ] 枢轴更大OrEqualToPivot

顺便说一句，第一行有一个错误：

int 中间 = ( 低 + 高 ) / 2; //错误的int middle = ( low + high ) >>> 1; //正确的

原因是如果 (low + high) 大于 Integer.MAX_VALUE 您将有溢出，而中间将是一个负数。第二行总是会给你一个积极的结果。