随机快速排序 IndexOutOfBounds 异常

Question

这是我想出的 QuickSort Randomized，但它不断抛出 IndexOutOfBounds 异常。我能帮忙吗？谢谢！

import java.util.Random;

public class QuickSort {

    void quickSort(int[] A, int start, int end) { // Initially: start = 0, end = n-1
        while (start < end) {
            int iOfPartition = randomisedPartition(A, start, end);
            if (iOfPartition - start < end - iOfPartition) {
                quickSort(A, start, iOfPartition - 1);
                start = iOfPartition + 1;
            } else {
                quickSort(A, iOfPartition + 1, end);
                end = iOfPartition - 1;
            }
        }
    }

    int randomisedPartition(int[] A, int start, int end) {
        Random rng = new Random();
        int randomNum = rng.nextInt(end + 1 - start) + start;
        swap(A, A[randomNum], A[start]);
        return hoarePartition(A, start, end);
    }

    int hoarePartition(int[] A, int start, int end) {
        int pivot = A[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (A[i] <= pivot && i < end) i++;
            while (A[j] > pivot && j > start) j--;
            if (i < j) swap(A, A[i], A[j]); 
        }
        swap(A, A[start], A[j]);
        return j; 
    }

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

我不断收到 arrayindexoutofbounds 错误。

Answer 1

我同意上面评论的观点，你应该学会使用调试器或打印语句来尝试拼凑正在发生的事情。

不过，我还是忍不住要调查一下。

看看你在调用 swap 时在做什么。您正在使用 A[randomNum]

获取位于 randomNum 位置的值

    swap(A, A[randomNum], A[start]); // incorrectly indexing here

但是在 swap 内部，你在重复这个过程，并取 A[A[randomNum]] 的值，它不一定存在。

int temp = A[i]; // indexing here again

所以你的问题是你错误地索引了两次。您应该只在交换函数中使用 []，而不要在 randomisedPartition 函数中使用。 randomisedPartition 应该发送交换索引，而不是索引值。

我是怎么想出来的？我尝试使用非常简单的数据进行调用

int data[] = {5,3,4};
new Example().quickSort(data, 0, 2);

并得到索引越界 5 错误。这就是你调试的方式。

随机快速排序 IndexOutOfBounds 异常

Randomized QuickSort IndexOutOfBounds exception

java

random

quicksort

indexoutofboundsexception

arrayindexoutofboundsexception