algorithm - 双枢轴快速排序算法

Question

我正在分析 java 中 Arrays.sort() 方法的代码。我的问题是整数数组 a[] 的什么值将返回 true ？

     if (less < e1 && e5 < great) 

递归地对左右部分进行排序后，排除数组 a[] 的什么值的已知枢轴，中心部分会变得太大(包括数组的 > 4/7)吗？

给定 QUICKSORT_THRESHOLD = 286 。 数组大小不能超过286

请提供 int 数组的任何示例。

Answer 1

当所有候选枢轴都接近数组的最大值或最小值时，就会发生这种情况。

java.util.DualPivotQuicksort#sort() 从数组中的 5 个位置选择枢轴:

    int seventh = (length >> 3) + (length >> 6) + 1;
    int e3 = (left + right) >>> 1; // The midpoint
    int e2 = e3 - seventh;
    int e1 = e2 - seventh;
    int e4 = e3 + seventh;
    int e5 = e4 + seventh;

所以，为了构造一个满足条件的数组，我们需要用极值填充这5个位置。例如:

int[] x = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2,  /* e1 = 10 */
    0, 0, 0, 0, 0, 0, -1,              /* e2 = 17 */
    0, 0, 0, 0, 0, 0, 0,               /* e3 = 24 */
    0, 0, 0, 0, 0, 0, 1,               /* e4 = 31 */
    0, 0, 0, 0, 0, 0, 2,               /* e5 = 38 */
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
Arrays.sort(x);

还有一个重要的案例，其中该方法在排序之前更改了中心部分的边界:

int[] x = {
        70, 66, 11, 24, 10, 28, 58, 13, 19, 90, 15,
        79, 16, 69, 39, 14, 10, 16,
        40, 59, 47, 77, 90, 50, 50,
        50, 16, 76, 86, 70, 33, 90,
        24, 35, 73, 93, 87, 19, 91,
        73, 87, 22, 15, 24, 92, 34, 35, 98, 11, 40
};