时间戳

首页 > 解决方案 > QuickSort 方法中的 java.lang.IllegalArgumentException

java - QuickSort 方法中的 java.lang.IllegalArgumentException

问题描述

我正在遵循以下伪代码：

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 中实现它时，我插入代码：

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

}

系统在屏幕上向我显示以下错误：

在 alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:43) 的 alg.quicksort 的 java.util.Arrays.copyOfRange(Arrays.java:3591) 的线程“main”中出现异常 java.lang.IllegalArgumentException: 5 > 4。 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

错误在行中： 

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

有人可以帮我吗？

标签： javaalgorithmsortingquicksort

解决方案

首先，两条线

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

错了。您不得复制数组。这将阻止快速排序算法工作，因为您在递归调用中对临时副本进行排序。排序后的子数组将被丢弃。

程序中的另一个错误引发了异常：的第三个参数Arrays.copyOfRange是排他性的。即它不会将元素复制from到，to而是复制from到to - 1. 但是您已经从上限中减去了一个，并且在快速排序中，可能会发生其中一个子数组的size 为零。在这种情况下，要复制的范围变为负数。那是个例外。

还有第三个错误：您交换了伪代码的前两行。这将在空数组上崩溃。

最后，您不能以伪代码中所示的这种方式实现快速排序算法，因为 Java（与例如 C 不同）不支持数组切片。

您需要修改算法，将其拆分为两种方法：

  • 对数组切片进行递归排序的一种方法：
    请注意，我将数组 start 和 end 替换为fromand to。

    public static void quickSort(int[] array, int from, int to) {
  if (array.length <= 1)
    return;
  int pivot = array[to];
  int left = from;
  int right = to;
  while (left <= right) {
    while (array[left] < pivot)
      left++;
    while (array[right] > pivot)
      right--;
    if (left <= right) {
      swap(array[left], array[right]);
      right--;
      left++;
    }
    quickSort(array, from, right);
    quickSort(array, left, to);
  }
}

  • 第二种方法对整个数组进行排序，该方法为整个数组调用上述方法。

    public static void quickSort(int[] array) {
  return quickSort(array, 0, array.length - 1);
}

推荐阅读