QuickSort方法中的java.lang.IllegalArgumentException [英] java.lang.IllegalArgumentException in QuickSort method

问题描述

我正在遵循以下伪代码:

I am following the following pseudocode:

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

但是当我尝试在Java中实现它时，我会插入代码:

but when I try to implement it in java, I insert code:

import java.util.Arrays;

public class ALGQuickSort {

public static void main(String[] args) {
    int[] array = {6, 3, 4, 8, 9, 10, 1};
    quickSort(array);
    System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array) {
    int pivot = array[array.length - 1];
    if (array.length > 1) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array[left], array[right]);
                right--;
                left++;
            }
            int[] array1 = Arrays.copyOfRange(array, 0, right);
            int[] array2 = Arrays.copyOfRange(array, left, array.length - 1);
            quickSort(array1);
            quickSort(array2);

        }
    }

}

public static void swap(int a, int b) {
    int aux = a;
    a = b;
    b = aux;
}

}

系统在屏幕上显示以下错误:

the system shows me the following error on the screen:

线程"main"中的异常java.lang.IllegalArgumentException:5> 4 在java.util.Arrays.copyOfRange(Arrays.java:3591)在 alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:43)在 alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:44)在 alg.quicksort.ALGQuickSort.main(ALGQuickSort.java:21) C:\ Users \ Alex \ AppData \ Local \ NetBeans \ Cache \ 8.2 \ executor-snippets \ run.xml:53: Java返回:1

Exception in thread "main" java.lang.IllegalArgumentException: 5 > 4 at java.util.Arrays.copyOfRange(Arrays.java:3591) at alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:43) at alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:44) at alg.quicksort.ALGQuickSort.main(ALGQuickSort.java:21) C:\Users\Alex\AppData\Local\NetBeans\Cache\8.2\executor-snippets\run.xml:53: Java returned: 1

该错误在该行中:

int[] array2 = Arrays.copyOfRange(array, left, array.length - 1);

有人可以帮助我吗?

推荐答案

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

Improvements/corrections to your quick-sort algorithm:

1. 更正您的交换方法:您使用的交换方法将不起作用.
2. 递归调用应该在for循环之外:您的伪代码是正确的，但在您的实现中并非如此.
3. 将数据透视表放置在正确的位置，然后对现在(确保)不应包含数据透视元素的子数组进行递归调用.在while循环之后，请确保right+1 == left(想一想，您将理解为什么这是正确的).现在将array [left]与数据透视元素交换，并递归调用2个不同的子数组(数据透视图的左侧子数组为beginIndex..right，数据透视图的右侧子数组为left+1..endIndex，在此我假设您需要排序array[beginIndex..endIndex])
4. 避免复制:最好避免复制数组的一部分(相反，您可以传递startIndex和endIndex来表示要排序的子数组)
5. 使用随机快速排序:如果您不总是选择最后一个元素作为数据透视表，这也会更好(您可以在开始排序之前选择任何随机元素，然后然后将其与数组的最后一个元素交换.使用此策略，您无需在现有代码中进行太多更改)选择 random element as pivot (随机元素作为枢轴点)会更好.参见此链接以获取更多详细信息.
6. 将交换方法设置为私有:与算法无关，但最好将交换方法设置为私有，因为您可能不打算从此类的外部调用它.

1. Correct your swap method: The swap method that you are using will not work.
2. The recursive call should be outside the for loop: Your pseudo-code is correct, but in your implementation it is not the case.
3. Place the Pivot at its correct position and then have a recursive call on sub-arrays that now (for-sure) should not contain the pivot element. After the while loop, you are sure that right+1 == left (think on it a bit and you will understand why this is true). Now swap the array[left] with pivot element and give a recursive call on 2 different sub-arrays (left sub-array to the pivot is beginIndex..right and right sub-array to the pivot is left+1..endIndex where I assume that you need to sort array[beginIndex..endIndex])
4. Avoid copying: Its better to avoid copying a part of the array (instead you can pass the startIndex and the endIndex to denote the sub-array you want to sort)
5. Use Randomized Quick sort: It would also be better if you don't always select the last element as your pivot (what you can do here is just before starting to sort select any random element and then swap it with the last element of your array. Using this strategy you don't have to make much changes in your existing code) This selection of random element as pivot is much better. See this link for more details.
6. Make swap method private: Not relevant to the algorithm, but it is good if you make the swap method private as you might not intend to call it from outside of this class.

如果您打算将索引为index1和index2的数组元素互换，那么以下代码将起作用:

If you intend to swap the elements of array with index say index1 and index2, then the following code will work:

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

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

The following is the final code with all the above suggested changes:

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

这篇关于QuickSort方法中的java.lang.IllegalArgumentException的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！