Quicksort不运行Java

Question

我试图做一个快速排序，但它总是显示错误的ArrayIndexOutOfBoundsException。

public class Quicksort
{
    void sort(int[] arr)
    {
        _quicksort(arr, 0, arr.length - 1);
    }
    private void _quicksort(int[] arr, int left, int right)
    {
        int pivot = (left + right)/2;
        int l = left;
        int r = right;
        while (l <= r)
        {
            while (arr[l] < pivot)
            {
                l++;
            }
            while (arr[r] > pivot)
            {
                r--;
            }
            if(l <= r)
            {
                int temp = l;
                l = r;
                r = temp;
                l++;
                r++;
            }
        }
        if(left < r)
        {
            _quicksort(arr, left, r);
        }
        if(l < right)
        {
            _quicksort(arr, l, right);
        }
    }
}

有人知道为什么它不运行吗？它总是会产生错误。

错误信息是

java.lang.ArrayIndexOutOfBoundsException: -1
    at Quicksort._quicksort(Quicksort.java:18)
    at Quicksort._quicksort(Quicksort.java:33)
    at Quicksort.sort(Quicksort.java:5)

错误消息

Answer 1

您的代码似乎有几个问题。我把它们列在下面：

1. 变量pivot存储的是透视元素的索引，而不是实际值。因此，您不能像在2嵌套while循环中所做的那样，使用pivot进行通信。您需要的是arr[pivot]而不是pivot。
2. 想象一下arr看起来像{1, 1, 1, 3, 2, 2, 2}。这里，pivot将等于3，即arr[pivot]将等于3。现在，在两个嵌套的while循环终止后，l将等于3，而r将保持为6。然后交换arr[l]和arr[r]，并同时增加l和r。由于l仍然小于r，所以外部while循环第二次运行，当控件到达第二个嵌套的when循环时，您将得到一个ArrayIndexOutOfBoundsExecption。发生这种情况是因为您试图访问arr[7] (超出界限)。

这是我的密码：

class Quicksort
{
    void sort(int[] arr)
    {
        myQuicksort(arr, 0, arr.length - 1);
    }

    private void myQuicksort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        int pivotIndex = (l + r) / 2;
        swap (arr, r, pivotIndex);

        int pivotValue = arr[r];
        int swapIndex = 0;
        int currentIndex = 0;

        while (currentIndex != r) {
            if (arr[currentIndex] < pivotValue) {
                swap(arr, currentIndex, swapIndex);
                swapIndex++;
            }

            currentIndex++;
        }

        swap(arr, r, swapIndex);

        myQuicksort(arr, l, swapIndex - 1);
        myQuicksort(arr, swapIndex + 1, r);
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class Main{
    public static void main(String[] args) {
        Quicksort quicksort = new Quicksort();

        int[] arr = {3, 7, 1, 0, 4};
        quicksort.sort(arr);

        for (int i : arr) {
            System.out.println(i);
        }
    }
}

你应该通读一下快捷键。但以下是要点：

1. 选择一个随机的枢轴元素，然后用最后一个元素交换它。这使得实现更加简单。
2. 循环输入数组，并跟踪swapIndex，这样在swapIndex之前的所有内容都小于pivotValue，从swapIndex到currentIndex的所有内容都大于(或等于) pivotValue。
3. 循环结束后，将swapIndex上的元素与pivot交换。这将插入pivot的正确位置。
4. pivot将数组划分为两个子数组。在这两个子数组上调用myQuicksort。