-1

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

我的做法是：

  1. 将枢轴设置为 start + (end-start) / 2 （而不是 start+end/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);
    }
}

编辑：如果您要对有效问题投反对票，请至少评论一下原因。

4

2 回答 2

1

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

  • 如果您没有在 while 中检查 i < end 和 j > start，在某些情况下您可能会遇到越界
  • 您选择枢轴位于子阵列的中间，但没有任何证据表明它在分区期间不会改变位置。然后，您使用旧的枢轴位置检查 k == 枢轴，这显然不起作用

希望这个对你有帮助。

于 2016-05-15T08:00:34.093 回答
0

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

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

我选择第一个元素（在开始时）作为枢轴，并在其前面创建一个“部分”，其中包含小于该枢轴的项目。然后，我将枢轴的值与值 < 枢轴部分中的最后一项交换。我将最终索引返回为枢轴点。

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

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);
    }
}
于 2016-05-15T08:22:08.477 回答