QuickSort 方法中的 java.lang.IllegalArgumentException

Question

<分区>

Answer 1

对您的快速排序算法的改进/更正:

1. 更正您的交换方法:您正在使用的交换方法将不起作用。
2. 递归调用应在 for 循环之外:您的伪代码是正确的，但在您的实现中并非如此。
3. 将枢轴放在正确的位置，然后对现在(肯定)不应包含枢轴元素的子数组进行递归调用。在 while 循环之后，您确定right+1 == left(稍微想一想，您就会明白为什么会这样)。现在将数组 [left] 与枢轴元素交换，并对 2 个不同的子数组进行递归调用(枢轴的左子数组是 beginIndex..right，枢轴的右子数组是left+1..endIndex 我假设您需要对 array[beginIndex..endIndex])
进行排序
4. 避免复制:最好避免复制数组的一部分(相反，您可以传递 startIndex 和 endIndex 来表示您要排序的子数组)
5. 使用随机快速排序:如果您不总是选择最后一个元素作为您的基准(您可以在这里做的是在开始排序之前选择任何随机元素并且然后将它与数组的最后一个元素交换。使用此策略，您不必对现有代码进行太多更改)这种选择随机元素作为枢轴的方法要好得多。参见 this链接了解更多详情。
6. 将交换方法设为私有(private):与算法无关，但最好将交换方法设为私有(private)，因为您可能不打算从此类外部调用它。

如果你打算用索引交换数组的元素，比如 index1 和 index2，那么下面的代码将起作用:

public static void swap(int[] array, int index1, int index2) {
    int aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}

以下是包含上述所有建议更改的最终代码:

public static void main(String[] args) {
    int[] array = {6, 30, 7, 23, 4, 8, 9, 10, 1, 90};
    quickSort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array, int beginIndex, int endIndex) {
    // System.out.println("called quick sort on the following : " + beginIndex + " " + endIndex);
    int arrayLength = endIndex - beginIndex + 1;
    int pivot = array[endIndex];
    if (arrayLength > 1) {
        int left = beginIndex;
        int right = endIndex - 1;
        while (left <= right) {
            // System.out.println(left + " " + right);
            while (left <= endIndex && array[left] < pivot) {
                left++;
            }
            while (right >= beginIndex && array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array, left, right);
                right--;
                left++;
            }

        }
        swap(array, left, endIndex); // this is crucial, and you missed it
        if (beginIndex < right) {
            quickSort(array, beginIndex, right);
        }
        if (left + 1 < endIndex) {
            quickSort(array, left + 1, endIndex);
        }
    }

}

private static void swap(int[] array, int index1, int index2) {
    int aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}