java - 快速排序不运行 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)

Error Message

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 循环会第二次运行，并且当控件到达第二个嵌套 while 循环。发生这种情况是因为您尝试访问 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 交换。这会将枢轴插入到正确的位置。

4. pivot 将数组分为 2 个子数组。对这 2 个子数组调用 myQuicksort。