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

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 的 "left" 元素。在我的特定情况下，我会将枢轴值递增 1 吗？有人可以解释我要实现的特定三中位数背后的逻辑吗？

Answer 1

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

使用 Hoare 类型分区方案，这是通过将主元索引设置为数组的中间，并根据需要与 [low] and/or [high] 交换以最终得到中位数来完成的array[pivot].

处的 3 个（低、中、高）元素

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

Implementing median-of-three into generic quicksort

java

arrays

sorting

quicksort