结合QuickSort和中位数选择算法

Question

我想修改QuickSort(在Java中)，这样每次调用Partition时，都会以比例数组的中值作为支点。

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

任何人都可以向我展示代码，看看它是如何完成的吗？

谢谢

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

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;
}

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

Answer 1

请注意，在< code>PARTITION中，< code>pivot是< code>A[r]。

public int QUICKSORT2(int[] A, int p, int r) {
    if (p<r) {
        int median=Math.floor((p + r) /2) - p + 1
        int q=SELECT(A, p, r, median)
        q=PARTITION2(A, p, r, q)
        QUICKSORT2(A, p, q-1)
        QUICKSORT2(A, q+1, r)
    }
}

public int PARTITION2(int[]A, int p, int r, int q) {
    int temp = A[r];
    A[r]=A[q];
    A[q]=temp;
    return PARTITION(A, p, r)
}

Answer 2

您正在寻找的是选择算法。这是一个带有伪代码的链接。

从链接：

在计算机科学中，选择算法是寻找列表中第k个最小数字的算法

要找到中值，您需要找到列表中k = floor((n-1)/2)最小的数字，其中n是列表的大小。

Answer 3

获取中位数的标准方法是对数据进行排序。你想通过对中位数进行分区来对数据进行排序。这对我来说似乎是鸡和蛋。

你能详细说说为什么你想对中位数进行分区/透视吗？