Quickselect实现不起作用

Question

我正在尝试编写代码来确定数组中最小的n个项。很难过，我正在与之斗争。根据我以前大学课本上的算法，这看起来是正确的。然而，很明显我做错了什么，因为它给了我一个堆栈溢出异常。

我的方法是：

1. 将枢轴设置为起始+（结束-起始）/2（而不是起始+结束/2以防止溢出）
2. 使用此位置的整数作为我将所有内容与之进行比较的轴心
3. 围绕这个枢轴迭代和交换所有内容，以便对内容进行排序（相对于枢轴排序）
4. 如果n==pivot，那么我认为我已经完成了
5. 否则，例如，如果我想要4个最小的元素，而枢轴是3，那么我需要从右边看（如果我想要第二小的元素，则从左边看）

-

public static void main(String[] args) {
    int[] elements = {30, 50, 20, 10};
    quickSelect(elements, 3);
}
private static int quickSelect(int[] elements2, int k) {
    return quickSelect(elements2, k, 0, elements2.length - 1);
}
private static int quickSelect(int[] elements, int k, int start, int end) {
    int pivot = start + (end - start) / 2;
    int midpoint = elements[pivot];
    int i = start, j = end;
    while (i < j) {
        while (elements[i] < midpoint) {
            i++;
        }
        while (elements[j] > midpoint) {
            j--;
        }
        if (i <= j) {
            int temp = elements[i];
            elements[i] = elements[j];
            elements[j] = temp;
            i++;
            j--;
        }
    }
    // Guessing something's wrong here
    if (k == pivot) {
        System.out.println(elements[pivot]);
        return pivot;
    } else if (k < pivot) {
        return quickSelect(elements, k, start, pivot - 1);
    } else {
        return quickSelect(elements, k, pivot + 1, end);
    }
}

编辑：如果你要否决一个有效的问题，请至少麻烦评论一下为什么。

Answer 1

这不会解决问题，但您的代码有几个问题：

• 如果不检查i<结束和j>开始的时候，在某些情况下你可能会碰到界外
• 您选择枢轴位于子阵列的中间，但没有任何东西可以证明它在分区过程中不会改变位置。然后，用旧的枢轴位置检查k==枢轴，这显然不起作用

希望这能有所帮助。

Answer 2

好吧，所以我做的第一件事就是修改如何获得我的枢轴/分区点。正如T.Claverie指出的那样，缺点是我使用的枢轴在技术上不是枢轴，因为元素的位置在分区阶段会发生变化。

实际上，我将分区代码重写为自己的方法，如下所示。这略有不同。

我选择第一个元素（在开始时）作为轴心，并在它前面创建一个"部分"，其中包含小于该轴心的项目。然后，我用values<枢轴。我返回最后的索引作为轴心点。

这可以进行更多清理（创建单独的交换方法）。

private static int getPivot(int[] elements, int start, int end) {
    int pivot = start;
    int lessThan = start;
    for (int i = start; i <= end; i++) {
        int currentElement = elements[i];
        if (currentElement < elements[pivot]) {
            lessThan++;
            int tmp = elements[lessThan];
            elements[lessThan] = elements[i];
            elements[i] = tmp;
        }
    }
    int tmp = elements[lessThan];
    elements[lessThan] = elements[pivot];
    elements[pivot] = tmp;
    return lessThan;
}

以下是称之为的例程

private static int quickSelect(int[] elements, int k, int start, int end) {
    int pivot = getPivot(elements, start, end);
    if (k == (pivot - start + 1)) {
        System.out.println(elements[pivot]);
        return pivot;
    } else if (k < (pivot - start + 1)) {
        return quickSelect(elements, k, start, pivot - 1);
    } else {
        return quickSelect(elements, k - (pivot - start + 1), pivot + 1, end);
    }
}