快速排序。处理重复项。

Question

有人能向我展示如何在我的函数中处理快速排序中的重复值吗？

private static int[] quickSort(int[] input, int left, int right) {
    int mid = (left + right) / 2;
    int i = left;
    int j = right;

    if((right - left) < 1) {
        return new int[]{};
    }

    while(i <= j) {
        while((input[i] < input[mid])) {
            i++;
        }

        while((input[j] > input[mid])) {
            j--;
        }

        if(i <= j) {
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
            i++;
            j--;
        }
    }

    if(j > left) {
        input = quickSort(input, left, j);
    }

    if(i < right) {
        input = quickSort(input, i, right);
    }
    return input;
}

- gran_profaci

---

你能举一个简单的例子，说明你的代码没有处理重复项，以及你希望它做什么吗？例如，如果我尝试对 1, 1, 0, 3 进行排序，它会抛出异常。 - Peter Lawrey

Answer 1

代码存在几个问题。

• "return new int[]{};" 这会生成新的数组并不必要地消耗内存。你可以返回 "input"。
• 对于第一个内部循环，你可能希望使用 "input[i] <= input[mid] && i < mid"。这将处理重复项。

这里有一些经过充分测试的代码: 快速排序

- user1931858