java - 将三中位数实现到通用快速排序中

Question

我一直在尝试在快速排序的实现中实现三中位数。我知道这可能不是快速排序的最佳实现，但不幸的是我被迫使用它。

public static <E extends Comparable<E>> void quickSort(E[] list){
    quickSort(list, 0, list.length - 1);
}

private static <E extends Comparable<E>> void quickSort(E[] list, int first, int last){
    if (last > first) {
        int pivotIndex = partition(list, first, last);
        quickSort(list, first, pivotIndex - 1);
        quickSort(list, pivotIndex + 1, last);
    }
}

private static <E extends Comparable<E>> int partition(E[] list, int first, int last){
    E pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {
        while (low <= high && (list[low].compareTo(pivot) <= 0)){
            low++;
        }

        while (low <= high && (list[high].compareTo(pivot) > 0)){
            high--;
        }

        if (high > low){
            E temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && (list[high].compareTo(pivot) >= 0)){
        high--;
    }

    if (pivot.compareTo(list[high]) > 0){
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else{
        return first;
    }
}

我首先所做的是将其更改为与通用数组一起使用。现在，我需要将枢轴设置为 list 数组中前三个值的中位数。

我了解如何获取前三个值的中位数。我不明白的是它如何影响这种快速排序实现的工作方式。

将枢轴设置为中值后，这对向前和向后搜索有何影响？在所示的代码中，low 设置为“左”元素并增加 1。在我的特定情况下，我是否会将主元值增加 1？有人可以解释我试图实现的特定三中位数背后的逻辑吗？

Answer 1

通常使用示例代码中所示的 Lomotu 类型方案，将 [low] 与 [middle] 和 [high] 值进行比较，并根据需要进行交换，以便中值最终为 array[low]。如果对已排序或​​反向排序的数组进行排序，这可以防止最坏的情况出现。使用前 3 个值的中位数并不能防止有序或逆序数据的最坏情况。

对于 Hoare 类型分区方案，这是通过将主元索引设置为数组的中间，并根据需要与 [low] 和/或 [high] 交换以最终得到中位数 3(low，中，高)数组[pivot]处的元素。