排序陣列使用堆排序

Question

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) 

我真的想現在什麼是錯的，但我失敗了PLZ任何一個能告訴我什麼是我錯了嗎？

對不起，我的英語不好

Answer 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; 
} 

Answer 2

兩個問題開始（會有更多）。

1）Java不是C.找到A的長度，使用A.length不傳遞單獨的變量。

2）你的l和r的計算被打破。你通過6/2 = 3然後你得到2*3和2*3+1（6和7）爲您的指示。這兩者都不是有效的。

Answer 3

我的猜測是，你的問題就在這裏：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; 

Answer 4

這爲我工作：

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] + " "); 
     } 

    } 

}