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

什么是頂堆？

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

如圖：

什么是堆排序(Heapsort)？

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

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

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

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

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

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

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

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

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

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

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

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

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

最后得到的大頂堆：

代碼實(shí)現(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.將形成的大頂堆最后一個(gè)元素和根進(jìn)行交換

在該例子中應(yīng)該是將2和6進(jìn)行交換，得到：

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

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

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

要進(jìn)行排序的部分：{2, 3, 5, 1, 0}

3.將除了最后一個(gè)結(jié)點(diǎn)剩下的完全二叉樹轉(zhuǎn)化成一個(gè)新的大頂堆

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

該例子中：index位置上的值是2，該位置的孩子結(jié)點(diǎn)分別為3 和 5，將2和5進(jìn)行交換之后，index = index * 2 + 2 = 2，此時(shí)index位置結(jié)點(diǎn)是一個(gè)葉子結(jié)點(diǎn)，不再進(jìn)行交換，此時(shí)構(gòu)成了一個(gè)新的大頂堆。如圖：

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

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

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

/**
 * @author LZD   2018/03/01
 */
public class HeapSort {
  public static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2)
      return;
    // 構(gòu)建大頂堆
    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) {
    // 先判斷當(dāng)前的index位置的結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)
    int left = index * 2 + 1;
    while(left < heapSize) {
      // 不是葉子結(jié)點(diǎn)則選出index位置結(jié)點(diǎn)的孩子結(jié)點(diǎn)中較大的賦給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);
  }
}

總結(jié)

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

最新評論