Quickselect 实现不起作用

Question

我正在尝试编写代码来确定数组中的第 n 个最小项。很遗憾我正在为此苦苦挣扎。根据我当年大学教科书中的算法，这看起来是正确的。但是，显然我做错了什么，因为它给了我一个堆栈溢出异常。

我的做法是：

将枢轴设置在 start + (end-start) / 2（而不是 start+end/2 以防止溢出）
使用这个位置的整数作为我比较所有内容的基准
迭代并交换围绕此枢轴的所有内容，以便对事物进行排序（相对于枢轴排序）
如果 n == pivot，那么我想我完成了
否则，如果我想要第 4 个最小的元素并且枢轴是 3，例如，那么我需要在右侧查看（如果我想要第 2 个最小的元素，则需要在左侧查看）。

-

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 < end 和 j > 开始，在某些情况下您可能运行出界
你选择你的枢轴在子数组的中间，但没有任何证据证明它在分区时不会改变位置。然后，你用旧的枢轴位置检查 k == pivot，这显然行不通

希望对您有所帮助。

Answer 2

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

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

我选择第一个元素（在开始处）作为基准，并在其前面创建一个 "section"，其中的项目小于该基准。然后，我将枢轴的值与值 < 枢轴部分中的最后一项交换。我 return 最终索引作为枢轴点。

这可以进一步清理（创建单独的交换方法）。

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

Quickselect 实现不起作用

Quickselect implementation not working

java

algorithm

quicksort

quickselect