java - 快速排序。处理重复

Question

有人可以告诉我如何使用我的函数在 QuickSort 中处理重复项吗？

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

Answer 1

代码有几个问题。

• “返回新的 int[]{};” 这将生成新的数组并不必要地消耗内存。您可以返回“输入”。
• 对于第一个内部循环，您可能需要“input[i] <= input[mid] && i < mid”。这将处理重复项。

这里有一些经过良好测试的代码：快速排序