0 
class HeapSort{
   public static void main(String args[]){
      int A[]={6,5,4,3,2,1};
      HeapSor obj=new HeapSor(6);
      obj.Heap_Sort(A);
      obj.print(A);
   }
}


class HeapSor{

    int lenOfArray;
    int HeapSize;

    HeapSor(int len){
    this.lenOfArray=len;
    this.HeapSize=len;
    }

    void Heap_Sort(int A[]){
    for(int i=0; i<lenOfArray; i++){
        BuiltHeap(A);
        HeapSize--;
        swap(A,i,lenOfArray-i);
    }
    }

    void BuiltHeap(int A[]){
    for(int i=lenOfArray/2; i>=0; i--)
        MaxHeapify(A,i);
    }

    void MaxHeapify(int A[],int i){
    int l=2*i;
    int r=2*i+1;
    int max=i;

    if(i>HeapSize)
        return;
    if(A[l]>A[r])
        max=l;
    else
        max=r;

    if(A[i]<A[max])
        swap(A,i,max);
    //max=i;
    }

    void swap(int A[],int i,int j){
    if(i==j)
        return;

    int temp=A[i];
    A[i]=A[j];
    A[j]=temp;
    }

    void print(int A[]){
    for(int i=0; i<lenOfArray; i++)
        System.out.print(A[i]+" ");

    System.out.println();
    }
}

当我编译它给了我这个错误

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at HeapSor.MaxHeapify(HeapSort.java:41)
    at HeapSor.BuiltHeap(HeapSort.java:31)
    at HeapSor.Heap_Sort(HeapSort.java:23)
    at HeapSort.main(HeapSort.java:5)

我真的很想知道现在出了什么问题，但我失败了请任何人告诉我我的问题是什么？

对不起，我的英语不好

4

4 回答 4

2

两个问题开始（会有更多）。

1）Java不是C。查找A使用A.length不传递单独变量的长度。

2）你对 l 和 r 的计算被打破了。你传入6/2=3然后你得到2*3和2*3+1(6和7) 作为你的索引。这些都不是有效的。

于 2013-02-07T21:43:28.497 回答
1

我的猜测是你的问题在这里： void MaxHeapify(int A[],int i)

您分配左右孩子： 

int l=2*i;  
int r=2*i+1;

但是您不检查它们是否超出范围。你检查i. 

if(i>HeapSize)  
        return;

但2*i可能超出范围，您可以使用它： 

 if(A[l]>A[r])  
        max=l;  
    else  
        max=r;
于 2013-02-07T21:44:16.650 回答
1 
void max_heapify(int a[],int i,int n) {
    int mxPos = i;
    int l = i*2; // left child
    int r = i*2+1; // right child

    if( l <= n and a[l] > a[mxPos] ) mxPos = l;
    if( r <= n and a[r] > a[mxPos] ) mxPos = r;

    if( mxPos != i ) {
        swap( a[i] , a[mxPos] );
        max_heapify( a , mxPos , n );
    }
}

void build_max_heap( int a[] ,int n) {
    for(int i = n / 2 ; i >= 1 ; i-- ) max_heapify(a,i,n);
}

void heapsort(int a[],int n) {
    build_max_heap(a,n);
    for( int i = n ; i >= 2 ; i-- ) {
        swap( a[1] , a[i] );
        n--;
        max_heapify( a , 1 , n );
    }
}

int main() {
    int n , a [100] ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
    heapsort(a,n);
    for( int i = 1 ; i <= n ; i++ ) cout << a[i] << endl;
}
于 2014-07-16T00:13:46.987 回答
0

这对我有用：

package Heap;

public class HeapSort {

    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;

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

    public static void maxheap(int[] a, int i) {
        left = 2 * i;
        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) {
            exchange(i, largest);
            maxheap(a, largest);
        }
    }

    public static void exchange(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void sort(int[] a0) {
        a = a0;
        buildheap(a);

        for (int i = n; i > 0; i--) {
            exchange(0, i);
            n = n - 1;
            maxheap(a, 0);1
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a1 = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        sort(a1);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i] + " ");
        }

    }

}
于 2015-09-16T05:57:49.420 回答