Java排序算法總結之堆排序

Java排序算法總結之堆排序。本站提示廣大學習愛好者：（Java排序算法總結之堆排序）文章只能為提供參考，不一定能成為您想要的結果。以下是Java排序算法總結之堆排序正文

本文實例講述了Java排序算法總結之堆排序。分享給年夜家供年夜家參考。詳細剖析以下：

1991年盤算機前驅獎取得者、斯坦福年夜學盤算機迷信系傳授羅伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年配合創造了有名的堆排序算法( Heap Sort )。本文重要引見堆排序用Java來完成。

聚積排序(Heapsort)是指應用聚積樹（堆）這類材料構造所設計的一種排序算法，可以應用數組的特色疾速定位指定索引的元素。堆排序是不穩固的排序辦法，幫助空間為O(1)， 最壞時光龐雜度為O(nlog2n) ，堆排序的堆序的均勻機能較接近於最壞機能。

堆排序應用了年夜根堆(或小根堆)堆頂記載的症結字最年夜(或最小)這一特點，使得在以後無序區當選取最年夜(或最小)症結字的記載變得簡略。

（1）用年夜根堆排序的根本思惟

① 先將初始文件R[1..n]建成一個年夜根堆,此堆為初始的無序區
② 再將症結字最年夜的記載R[1](即堆頂)和無序區的最初一個記載R[n]交流，由此獲得新的無序區R[1..n-1]和有序區R[n]，且知足R[1..n-1].keys≤R[n].key
③因為交流後新的根R[1]能夠違背堆性質，故應將以後無序區R[1..n-1]調劑為堆。然後再次將R[1..n-1]中症結字最年夜的記載R[1]和該區間的最初一個記載R[n-1]交流，由此獲得新的無序區R[1..n-2]和有序區R[n-1..n]，且仍知足關系R[1..n-2].keys≤R[n-1..n].keys，異樣要將R[1..n-2]調劑為堆。
……
直到無序區只要一個元素為止。
（2）年夜根堆排序算法的根本操作：
① 初始化操作：將R[1..n]結構為初始堆；
② 每趟排序的根本操作：將以後無序區的堆頂記載R[1]和該區間的最初一個記載交流，然後將新的無序區調劑為堆(亦稱重建堆)。
留意：
①只需做n-1趟排序，選出較年夜的n-1個症結字便可以使得文件遞增有序。
②用小根堆排序與應用年夜根堆相似，只不外其排序成果是遞加有序的。堆排序和直接選擇排序相反：在任什麼時候刻堆排序中無序區老是在有序區之前，且有序區是在原向量的尾部由後往前慢慢擴展至全部向量為止。

代碼完成：

public class Test { 
  public static int[] Heap = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
  // 預設數據數組 
  public static void main(String args[]) { 
    int i; // 輪回計數變量 
    int Index = Heap.length; // 數據索引變量 
    System.out.print("排序前: "); 
    for (i = 1; i < Index - 1; i++) 
      System.out.printf("%3s", Heap); 
    System.out.println(""); 
    HeapSort(Index - 2); // 堆排序 
    System.out.print("排序後: "); 
    for (i = 1; i < Index - 1; i++) 
      System.out.printf("%3s", Heap); 
    System.out.println(""); 
  } 
  /** 
   * 樹立堆 
   */ 
  public static void CreateHeap(int Root, int Index){
    int i, j; // 輪回計數變量 
    int Temp; // 暫存變量 
    int Finish; // 斷定堆能否樹立完成 
    j = 2 * Root; // 子節點的Index 
    Temp = Heap[Root]; // 暫存Heap的Root 值 
    Finish = 0; // 預設堆樹立還沒有完成 
    while (j <= Index && Finish == 0) { 
      if (j < Index) // 找最年夜的子節點 
        if (Heap[j] < Heap[j + 1]) 
          j++; 
      if (Temp >= Heap[j]) 
        Finish = 1; // 堆樹立完成 
      else { 
        Heap[j / 2] = Heap[j]; // 父節點 = 今朝節點
        j = 2 * j; 
      } 
    } 
    Heap[j / 2] = Temp; // 父節點 = Root值 
  } 
  public static void HeapSort(int Index) { 
    int i, j, Temp; 
    // 將二叉樹轉成Heap 
    for (i = (Index / 2); i >= 1; i--) 
      CreateHeap(i, Index); 
    // 開端停止堆排序 
    for (i = Index - 1; i >= 1; i--) {   
      Temp = Heap; // Heap的Root值和最初一個值交流 
      Heap = Heap[1];   
      Heap[1] = Temp;   
      CreateHeap(1, i); // 對其他數值重建堆   
      System.out.print("排序中: ");   
      for (j = 1; j <= Index; j++)   
      System.out.printf("%3s",Heap[j]);   
      System.out.println("");   
    }
  }
}

堆可以被算作是一棵樹，結點在堆中的高度可以被界說為從本結點到葉子結點的最長簡略降低途徑上邊的數量；界說堆的高度為樹根的高度。我們將看到，堆構造上的一些根本操作的運轉時光至少是與樹的高度成反比，為O（lgn）。經由過程浏覽本文，願望能贊助到你。

願望本文所述對年夜家的java法式設計有所贊助。