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 导致整数溢出。