java中實現堆排序的原理是什么

本篇文章為大家展示了java中實現堆排序的原理是什么，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

堆是一個數組，被看成一個近似完全二叉樹。

舉例說明：

堆的性質：

1.已知元素在數組中的序號為i

其父節點的序號為 i/2的整數
其左孩子節點的序號為2*i
其右孩子節點的序號為2*i+1

2.堆分為最大堆和最小堆

在最大堆中，要保證父節點的值大于等于其孩子節點的值
在最小堆中，要保證父節點的值小于等于其孩子節點的值

java實現堆排序

public class MyHeapSort {
  public void Heap_Sort(int[] A) {
    /**
     * 這個函數完成堆排序
     * 先構建一個最大堆
     * 將數組中第一個元素和最后一個交換，
     * 堆的長度減一
     * 在從第一個位置開始保證堆的性質調用Max_heapify()函數。
     * 這樣保證目前最大的元素在數組的最后位置。
     * 以此類推，直到最后一個元素。
     */
    Build_Max_Heap(A);
    for (int i = A.length - 1; i >= 1; i--) {
      int temp = A[0];
      A[0] = A[i];
      A[i] = temp;
      Max_heapify(A, 0, i);
    }
  }
  public void Build_Max_Heap(int[] A) {
    /**
     * 這個函數用來構建堆
     * A:待排序的數組
     * （for循環中i的值從數組長度的一般開始取，是因為完全二叉樹的性質，
     * 一半的節點葉根節點所以從葉節點開始向上遍歷來保證堆的性質）
     */
    for (int i = A.length/2; i >= 0; i--) {
      Max_heapify(A, i, A.length);
    }
  }
  public void Max_heapify(int[] A, int i, int heap_size) {
    /**這個函數用來維護堆的性質，
     * 保證以序號為i的元素為根節點的子樹中，父節點的值大于其孩子節點的值。
     * A:待排序數組
     * i：在數組A中的序號
     * heap_size:堆的大小
     */
    int largest = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    if (l < heap_size && A[l] > A[i]) largest = l;
    if (r < heap_size && A[r] > A[largest]) largest = r;
    if (largest != i) {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
      Max_heapify(A, largest, heap_size);
    }
  }
  public static void main(String[] args) throws Exception {
    System.out.println("億速云測試結果：");
    int[] a = new int[]{1,3,2,5,34,23,44,15,67,45};
    new MyHeapSort().Heap_Sort(a);
    for (int x : a) System.out.println(x);
  }
}

代碼中例子的運行結果：

Java是什么

Java是一門面向對象編程語言，可以編寫桌面應用程序、Web應用程序、分布式系統和嵌入式系統應用程序。

上述內容就是java中實現堆排序的原理是什么，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。