在java代碼中進行堆排序？

Question

我正在嘗試一些堆在java中的樂趣。

首先，我創建一個最大堆。然後將第一個元素設置爲變量max，將最後一個項目從未安排的數組移動到堆頂部，然後按下。

我試過21個元素，它可以正常工作70％，我想知道是否有人發現問題。

謝謝。

public class HeapSort extends Sort{ 
    public int sort(int arr[]) { 
     for (int i = 1; i < arr.length; i++) { 
      // add to heap 
      int p = i; 
      int pp = p /2 ; 
      while (p > 0 && arr[pp] < arr[p]) { 
       swap(arr, p, pp); 
       p = pp; 
       pp = p/2; 
      } 

     } 

     for (int i = arr.length - 1; i > 0; i--) { 
      swap(arr, 0, i); 
      int p = 0; 
      int child1 = (p << 1) + 1; 
      int child2 = (p << 1) + 2; 

      while (child2 < i || child1 < i) { 
       if (child1 >= i) { 
        if (arr[p] < arr[child2]) { 
         swap(arr, p, child2); 
         p = child2; 
        } else { 
         break; 
        } 
       } else if (child2 >= i) { 
        if (arr[p] < arr[child1]) { 
         swap(arr, p, child1); 
         p = child1; 
        } else { 
         break; 
        } 
       } else { 
        int minIdx = arr[child1] < arr[child2] ? child1 : child2; 
        int maxIdx = child1 == minIdx ? child2 : child1; 

        if (arr[p] < arr[maxIdx]) { 
         swap(arr, p, maxIdx); 
         p = maxIdx; 
        } else { 

         break; 

        } 
       } 
       child1 = (p << 1) + 1; 
       child2 = (p << 1) + 2; 
      } 

     } 
     return 0; 

    } 
    void swap(int arr[], int idx1, int idx2) { 
     int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp; 
    } 
    public String toString() { 
     return "HeapSort"; 
    } 

} 

Answer 1

您在堆排序的第一步中沒有正確構建堆。您需要在將基於零的數組除以兩之前減去一個。

public class HeapSort extends Sort{ 
    public int sort(int arr[]) { 
     for (int i = 1; i < arr.length; i++) { // add to heap 
     int p = i; 
     // int pp = p /2 ; <======= Problem! 
     int pp = (p-1)/2; 
     while (p > 0 && arr[pp] < arr[p]) { 
      swap(arr, p, pp); p = pp; 
      // pp = p/2; // <=====Problem! 
      pp = (p-1) /2; 

}