Quicksort无法运行Java

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

1. 该变量pivot存储枢轴元素的索引，而不存储实际值。因此，不能pivot像在两个嵌套的while循环中那样进行比较。您需要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循环将第二次运行，并且ArrayIndexOutOfBoundsExecption当控件到达第二个嵌套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);
        }
    }
}

您应该阅读Quicksort。但是这里是要点：

1. 选择一个随机的枢轴元素并将其与最后一个元素交换。这使实现更加简单。

2. 循环遍历输入数组，并跟踪a swapIndex，使得之前的所有内容都swapIndex小于，pivotValue而从到swapIndex之前的所有内容currentIndex均大于（或等于）pivotValue。

3. 循环用完后，将处的元素swapIndex替换为pivot。这会将插入pivot正确的位置。

4. 所述pivot划分成阵列的子阵列2。调用myQuicksort这两个子数组。