java - 结合快速排序和中值选择算法

Question

我想修改 QuickSort(Java 中的)，以便每次调用 Partition 时，都使用比例数组的中位数作为基准。

我有一个 Java 中值选择算法，它返回第 k 个最小元素，在本例中为中值。我在java中有大量的快速排序算法，它们都独立工作并对数组进行排序。不幸的是，我无法将这两者结合起来以实现上述目标...每次我尝试它时，我通常都会遇到 stackoverflow 错误。

有人可以向我展示代码以了解如何完成吗？

谢谢

编辑:例如，这是我尝试使用的中值选择算法。

public int quickSelect(int[] A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Partition(A,p,r);
    int len = q-p+1;

    if (k == len) return A[q];
    else if (k<len) return Select(A,p,q-1,k);
    else return Select(A,q+1,r,k-len);
}

public int partition(int[]A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j = p; j<=r-1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

它本身可以工作，但是当我尝试通过快速排序的分区函数调用快速选择以返回要使用的枢轴时，它不起作用。显然我做错了什么，但我不知道是什么。不幸的是，在互联网上，我没有找到任何将中值选择与快速排序结合起来的算法，即使是伪代码。

Answer 1

获取中位数的标准方法是对数据进行排序。您希望通过按中位数分区对数据进行排序。对我来说，这似乎是先有鸡还是先有蛋。

您能否详细说明为什么要在中位数上进行分区/旋转？