在介紹堆排序前，我們需要了解一下一種數(shù)據(jù)結構 —— 頂堆。

什么是頂堆？

它是一顆完全二叉樹，頂堆有大頂堆和小頂堆兩種。所謂大頂堆就是在這顆完全二叉樹中，任何一顆子樹都滿足：父結點的值 > 孩子結點的值；小頂堆則相反。

如圖：

什么是堆排序(Heapsort)？

利用堆積樹（堆）這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點快速定位指定索引的元素。

現(xiàn)在給我們一個無序數(shù)組，我們將其從小到大排序，使用堆排序的實現(xiàn)步驟和思想如下：

• 1.讓這個數(shù)組變成一個大根堆
• 2.將最后一個位置和堆頂位置作交換
• 3.將堆的大小進行 -1 操作
• 4.將當前的堆變成一個大頂堆
• 5.回到2

看起來似乎很抽象，那我們現(xiàn)在用一個例子進行講解：假設一個整型數(shù)組arr = {2, 1, 3, 6, 0, 5}

1.將一個無序數(shù)組變成一個大頂堆存儲

如果使用完全二叉樹進行存儲數(shù)組，任意下標為index的結點的父結點的下標應該是(index-1)/2，其孩子結點的下標應分別為：(index * 2 + 1) 和 (index * 2 + 2) 。我們使用該結論創(chuàng)建一個大頂堆：

首先我們假設0位置上的數(shù)已經排好，將其放在這棵二叉樹的根位置，創(chuàng)建一個int類型變量 i 記錄當前指向的數(shù)組的下標，初始化值為1。

設置一個index初始化值 = i，將index和(index-1)/2位置的數(shù)進行比較，也就是和它的父結點進行比較，如果比父結點小就不變，并進行 i++，index = i；如果比父結點大就和父結點交換并且給index賦值為(index-1)/2，即指向原來位置的父結點，再將該值與當前結點的父結點進行比較…直到該結點值是小于該結點父結點的值或到根結點時停止。

以arr數(shù)組進行舉例：

0位置上的數(shù)是2，先認為它是已經排好的，i 和 index此時都為1，(index - 1)/2為0，所以將1和2進行比較，1 < 2 所以1位置上的數(shù)不變，執(zhí)行 i++, index = i；

 此時i 和 index值都為2，(index - 1)/2為0，所以講3 和 2進行比較，3 > 2所以將3和2進行交換，原數(shù)組就變?yōu)椋簕3, 1, 2, 6, 0, 5}，index = (index - 1)/2 = 0，當前結點是根節(jié)點，不再進行比較了，執(zhí)行 i++, index = i；

此時i 和 index值都為3，(index - 1)/2為 1，所以將 6 和 1 進行比較，6 > 1所以將6和2進行交換，原數(shù)組就變?yōu)椋簕3, 6, 2, 1, 0, 5}，index = (index - 1)/2 = 1，不是根節(jié)點，于是再將6 和 3進行比較，6 > 3，所以再交換6 和 3，原數(shù)組變?yōu)椋簕6, 3, 2, 1, 0, 5}，index = (index - 1)/2 = 0，當前結點是根節(jié)點，不再進行比較了，執(zhí)行 i++, index = i；
…….

以此類推最后得到的數(shù)組：{6, 3, 5, 1, 0, 2}

最后得到的大頂堆：

代碼實現(xiàn)：

  // 插入數(shù)使其形成大頂堆
  public static void heapInsert(int[] arr, int index) {
    while(arr[index] > arr[(index - 1)/2]) {
      swap(arr, index, (index - 1)/2);
      index = (index - 1)/2;
    }
  }

2.將形成的大頂堆最后一個元素和根進行交換

在該例子中應該是將2和6進行交換，得到：

得到的數(shù)組：{2, 3, 5, 1, 0, 6}

那我們?yōu)槭裁匆M行交換呢？

這時候的數(shù)組最后一個值就是最大的了，也就是最后一個位置上的數(shù)已經排好了，接下來我們就要將除了最后位置的結點之外剩下的完全二叉樹進行排序了，即：

要進行排序的部分：{2, 3, 5, 1, 0}

3.將除了最后一個結點剩下的完全二叉樹轉化成一個新的大頂堆

傳入當前數(shù)組，并標記當前位置index，初始化值為0，先判斷當前的index位置的結點是否是葉子結點，如果是葉子結點就不需要再比較了，直接返回；如果不是葉子結點，則將index位置的值和它孩子結點的值進行比較，如果index位置上的值最大則不交換并且直接返回，否則選取最大的值與index位置上的值進行交換；交換后index為當前位置，再與當前位置的孩子結點進行比較。。。以此類推直到當前結點是一個葉子結點或不需要再交換時停止。

該例子中：index位置上的值是2，該位置的孩子結點分別為3 和 5，將2和5進行交換之后，index = index * 2 + 2 = 2，此時index位置結點是一個葉子結點，不再進行交換，此時構成了一個新的大頂堆。如圖：

得到的數(shù)組：{5, 3, 2, 1, 0, 6}

然后就回到了步驟2，直到數(shù)組中未排序的部分只有一個數(shù)時不再進行排序。

完整代碼實現(xiàn)：

/**
 * @author LZD   2018/03/01
 */
public class HeapSort {
  public static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2)
      return;
    // 構建大頂堆
    for(int i = 0;i < arr.length;i++) {
      heapInsert(arr, i);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while(heapSize > 0) {
      heapify(arr, 0, heapSize);
      swap(arr, 0, --heapSize);
    }
  }
  // 插入數(shù)使其形成大頂堆
  public static void heapInsert(int[] arr, int index) {
    while(arr[index] > arr[(index - 1)/2]) {
      swap(arr, index, (index - 1)/2);
      index = (index - 1)/2;
    }
  }
  // 將堆化為大頂堆
  public static void heapify(int[] arr, int index, int heapSize) {
    // 先判斷當前的index位置的結點是否是葉子結點
    int left = index * 2 + 1;
    while(left < heapSize) {
      // 不是葉子結點則選出index位置結點的孩子結點中較大的賦給largest
      int largest = left+1 < heapSize && arr[left + 1] > arr[left]
          ? left + 1: left;
      largest = arr[largest] > arr[index] ? largest : index;
      if(largest == index) {
        break;
      }
      swap(arr, largest, index);
      index = largest;
      left = index * 2 + 1;
    }
  }
  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
  // for test 打印數(shù)組
  public static void printArray(int[] arr) {
    for(int i = 0;i < arr.length;i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
  // for test
  public static void main(String[] args) {
    int[] arr = {2, 1, 3, 6, 0, 5};
    heapSort(arr);
    printArray(arr);
  }
}

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關內容請查看下面相關鏈接

最新評論