java - 如何编写快速排序分区函数

Question

这让我发疯，我知道这是一次性错误导致的，但由于某种原因，我的分区函数没有正确分区。我究竟做错了什么？

public static int partition(int numbers[], int lhs, int rhs) {
    int pivot = numbers[(rhs - lhs) / 2];
    int lIndex = lhs - 1;
    int rIndex = rhs + 1;

    while (true) {
        while (numbers[++lIndex] < pivot);
        while (numbers[--rIndex] > pivot);

        if (lIndex > rIndex) break;

        int temp = numbers[lIndex];
        numbers[lIndex] = numbers[rIndex];
        numbers[rIndex] = temp;
    }

    return lIndex;
}

Answer 1

最好找到枢轴（在您的情况下为中点）：

int pivot = numbers[lhs + (rhs - lhs) / 2];

如果 lhs 和 rhs 足够高，它可以防止 lhs+rhs 导致整数溢出。

Answer 2

这是一个问题：

int pivot = numbers[(rhs - lhs) / 2];

假设lhs= 100 和rhs= 120。上面将选择元素 (120 - 100) / 2 = 10 作为枢轴！

我想你想要类似的东西

int pivot = numbers[(rhs + lhs) / 2];

这至少会从您尝试分区的范围内选择一个枢轴！