我的Heap Sort代码在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中的数组是零索引的.您将循环上限(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数组的属性告诉您数组可以包含多少个元素,而不是最后一个元素的索引.