HeapSortコードの何が問題なのですか？

Question

私はJavaでヒープソート方法を書き込もうとしていますが、私がそれをしたいとまったく働いていない：

public class HeapSort { 

    private static int n; 

    private static void swap(int[] A, int a, int b) 
    { 
     int tmp = A[a]; 
     A[a] = A[b]; 
     A[b] = tmp; 
    } 

    private static void insert(int[] A, int i) 
    { 
     int left = i * 2; 
     int right = left + 1; 
     int max = i; 

     if (left <= n && A[left] < A[max]){ 
      max = left; 
     } 
     if (right <= n && A[right] > A[max]) { 
      max = right; 
     } 
     if (max != i) { 
      swap(A, i, max); 
      insert(A, max); 
     } 
    } 

    public static void HeapSort(int[] A) 
    { 
     n = A.length - 1; 

     for (int i = n/2; i >= 0; i--) 
      insert(A, i); 

     for (int i = n; i > 0; i--) { 
      swap(A, 0, i); 
      n--; 
      insert(A, 0); 
     } 
    } 

    public static void main(String[] args){ 
     int[] A = new int[] {9, 2, 8, 1, 4}; 
     System.out.println(java.util.Arrays.toString(arr)); 
     HeapSort(A); 
     System.out.println(java.util.Arrays.toString(arr)); 
    } 
} 

それは9、2、8、1、4のような配列を取得しますが、いくつかの配列で動作します1、4、2、8、9にソートされています。なぜ、配列を正しい方法でソートしていないのですか？

Answer 1

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

これを試してみてください。 私は以下のように完全なプログラムを作った。これはあなたが入力した入力に対してうまく機能します。ここ

public class HeapSort { 

private static int n; 

private static void swap(int[] A, int a, int b) 
{ 
    int tmp = A[a]; 
    A[a] = A[b]; 
    A[b] = tmp; 
} 

private static void insert(int[] A, int i) 
{ 
    int left = i * 2; 
    int right = left + 1; 
    int max = i; 

    if (left <= n && A[left] > A[i]){ 
     max = left; 
    } 
    if (right <= n && A[right] > A[max]) { 
     max = right; 
    } 
    if (max != i) { 
     swap(A, i, max); 
     insert(A, max); 
    } 
} 

public static void HeapSort(int[] A) 
{ 
    n = A.length - 1; 

    for (int i = n/2; i >= 0; i--) 
     insert(A, i); 

    for (int i = n; i > 0; i--) { 
     swap(A, 0, i); 
     n--; 
     insert(A, 0); 
    } 
} 

public static void main(String[] args){ 
    int[] A = new int[] {19, 6, 28, 1, 0}; 
    int[] B = new int[] {1, 2, 4, 8, 9, 0}; 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
    HeapSort(A); 
    HeapSort(B); 
    System.out.println(java.util.Arrays.toString(A)); 
    System.out.println(java.util.Arrays.toString(B)); 
} 

}

出力されます。

[19, 6, 28, 1, 0] 
[1, 2, 4, 8, 9, 0] 
[0, 1, 6, 19, 28] 
[0, 1, 2, 4, 8, 9] 

Answer 2

あなたがleft = i * 2を定義する場合は、あなたのヒープの根はA[1]、ないA[0]に格納する必要があります。インデックス0で配列を使用しないことにより、ノードiの左と右の子はそれぞれ2*iと2*i+1といつも言うことができます。

基本的にHeapSortには、0から1に変更する必要があります（4つあります）。配列{0, 9, 2, 8, 1, 4}でテストしてください。

また、insertの比較も間違っています。それはA[left] > A[max]である必要があります。