java - 我的 Java 堆排序代码有什么问题？

Question

我正在尝试在 Java 中使用此数组创建堆并对其进行排序。我的 maxHeap 函数中不断出现数组索引越界异常。该代码对我来说似乎很有意义，所以我不确定错误来自哪里。

有人知道我做错了什么吗？

 public static void main(String[] args) {
    int[] array = { 5, 16, 10, 7, 43, 12, 75, 33, 47, 3, 2489, 591, 6639, 557, 84, 9054, 17, 8841, 99, 701, 21, 78, 9, 36, 839};
    heapSort(array3);
    System.out.println("Heap Sort:");
    printArray(array3);
}

public static void createHeap(int []A){
    int n = A.length-1;
    for(int i=n/2;i>=0;i--){
        maxheap(A,i);
    }
}

public static void maxheap(int[] A, int i){ 
    int n = A.length;
    int largest;
    int left=2*i;
    int right=2*i+1;
    if(left <= n && A[left] > A[i]){
        largest=left;
    }
    else{
        largest=i;
    }

    if(right <= n && A[right] > A[largest]){
        largest=right;
    }
    if(largest!=i){
        int temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        maxheap(A, largest);
    }
}

public static void heapSort(int []A){
    createHeap(A);
    int n= A.length;
    for(int i=n;i>0;i--){
        int temp=A[0];
        A[0]=A[i];
        A[i]=temp;
        n=n-1;
        maxheap(A, 0);
    }
}


public static void printArray(int[] sortedArray) {

   for (int i = 0; i < sortedArray.length; i++) {
       System.out.print(sortedArray[i] + ", ");
   }
   System.out.println("");
}

Answer 1

Java 中的数组是 zero-indexed 。您将循环上限( n )设置为 A.length ，然后对其进行小于或等于比较，因此它始终会检查是否有太多元素。

if(left <= n && A[left] > A[i]){

应该是

if(left < n && A[left] > A[i]){

还有

if(right <= n && A[right] > A[largest]){

应该是

if(right < n && A[right] > A[largest]){

您还执行了一个狡猾的操作来初始化 right 。 createHeap()套i等于 n/2 (这本身可能是一个错误)。然后将此值传递给 maxHeap参数形式为i 。然后你就这样做:

int right = 2*i+1;

当 i 时会发生什么是说，2？

为了i成为2 , A.length必须是5或6 (因为 createHeap 将 n 设置为 A.length - 1 ，所以 (5 - 1) / 2 = 4 和 (6 - 1) / 2 一样)。当这逐渐渗透到maxheap时, 2 * i + 1带您前往 5 ，超出 A 的范围(可能是长度，但如果是这样，那么 4 是最高索引，而不是 5 )。

所以，这就是 A.length = 5 时的情况:

if(right <= n && A[right] > A[largest]) {
   ^ 5      ^ 5    ^ ArrayIndexOutOfBoundsException thrown here.

right <= n计算结果为true ，因为5确实等于 5 ，所以A[right]被评估，并立即失败并出现异常。对 right < n 进行简单的小于检查会阻止这种情况，如 5不小于5 ，因此第一个条件的计算结果为 false ，从而确保A[right]根本不会得到评估。

简而言之 - 这不适用于奇数长度数组。

记住:.length数组的属性告诉您数组可以包含多少个元素，而不是最后一个元素的索引。