怎么在Java中實現堆排序算法

怎么在Java中實現堆排序算法？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

什么是頂堆？

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

如圖：

什么是堆排序(Heapsort)？

利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。

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

• 1.讓這個數組變成一個大根堆

• 2.將最后一個位置和堆頂位置作交換

• 3.將堆的大小進行 -1 操作

• 4.將當前的堆變成一個大頂堆

• 5.回到2

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

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

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

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

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

以arr數組進行舉例：

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

 此時i 和 index值都為2，(index - 1)/2為0，所以講3 和 2進行比較，3 > 2所以將3和2進行交換，原數組就變為：{3, 1, 2, 6, 0, 5}，index = (index - 1)/2 = 0，當前結點是根節點，不再進行比較了，執行 i++, index = i；

此時i 和 index值都為3，(index - 1)/2為 1，所以將 6 和 1 進行比較，6 > 1所以將6和2進行交換，原數組就變為：{3, 6, 2, 1, 0, 5}，index = (index - 1)/2 = 1，不是根節點，于是再將6 和 3進行比較，6 > 3，所以再交換6 和 3，原數組變為：{6, 3, 2, 1, 0, 5}，index = (index - 1)/2 = 0，當前結點是根節點，不再進行比較了，執行 i++, index = i；
…….

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

最后得到的大頂堆：

代碼實現：

  // 插入數使其形成大頂堆
  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進行交換，得到：

得到的數組：{2, 3, 5, 1, 0, 6}

那我們為什么要進行交換呢？

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

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

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

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

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

得到的數組：{5, 3, 2, 1, 0, 6}

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

完整代碼實現：

/**
 * @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);
    }
  }
  // 插入數使其形成大頂堆
  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 打印數組
  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);
  }
}

關于怎么在Java中實現堆排序算法問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。