老生常談比較排序之堆排序

更新時間：2017年06月22日 09:17:35 投稿：jingxian

下面小編就為大家?guī)硪黄仙Ｕ劚容^排序之堆排序。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

對于堆排序會涉及一些完全二叉樹知識。對于待排序列{10, 2, 11, 8, 7}，把它看成是一顆完全二叉樹，如下圖所示。

堆分為大根堆和小根堆：大根堆表示每個根節(jié)點均大于其子節(jié)點（L(i) >= L(2i) && L(i) >= L(2i + 1)），小根堆表示每個根節(jié)點均小于其子節(jié)點（L(i) <= L(2i) && L(i) <= L(2i + 1)）。（在完全二叉樹中第i個節(jié)點的左子節(jié)點為2i，其右字節(jié)點為2i + 1）

本文將以大根堆的構建作為示例進行講解。

堆排序的第一步——構建初始堆。如何構建初始堆呢？根據定義，關鍵點在于每個根節(jié)點。觀察上述待排序列的完全二叉樹，不難發(fā)現存在節(jié)點2和節(jié)點10有子節(jié)點，它們是需要關注的節(jié)點。

如何定位節(jié)點2呢？發(fā)現它是葉子節(jié)點，或者最后一個節(jié)點的父節(jié)點，根據完全二叉樹的性質可知，除根節(jié)點外任意節(jié)點的父節(jié)點的編號為⌊n / 2⌋。已知n = 5，易知節(jié)點2的編號為⌊5 / 2⌋ = ②。比較它與左右子節(jié)點的大小并調整。

最后剩下根節(jié)點10，已知節(jié)點2的編號為②，② - 1 = ①即得到根節(jié)點10的編號。比較它與左右子節(jié)點的大小并調整。

調整完畢后發(fā)現已經構成了一個“大根堆”，示例中的待排序列較為簡單，再給出一個較為復雜的待排序列，觀察其構建大根堆的過程。對于待排序列{53, 17, 78, 09, 45, 65, 87, 32}，將它看成一顆完全二叉樹。

同樣我們來看它所需要關注的節(jié)點有哪些。

根據第一個例子，我們很容易能定位節(jié)點09的編號為⌊8 / 2⌋ = ④，節(jié)點78的編號為④ - 1 = ③……，依次類推，發(fā)現了一定的規(guī)律，即需要調整的節(jié)點位置從⌊n / 2⌋開始依次遞減直到根節(jié)點①結束(⌊n / 2⌋ ~ 1)?，F在開始調整。

在第四次調整結束后發(fā)現節(jié)點53不滿足大根堆的定義，其右子節(jié)點大于它，此時需要做進一步的向下調整。

注意向下調整是每次向上調整的時候都需要做的判斷是否需要向下調整，而不是在所有的向上調整結束過后再回過頭來向下調整。這樣大根堆就建立好了，此時待排序列數組情況已經發(fā)生了改變：{87, 45, 78, 32, 17, 65, 53, 09}。接下來是如何進行排序的問題。將大根堆的根節(jié)點與最后一個節(jié)點互換，并調整二叉樹使其仍然滿足大根堆。

可以看到將根節(jié)點與最后一個節(jié)點呼喚后，待排序列的最大值已經放到了數組的最后一個位置{……, 87}，此時完成了第一趟排序，但這第一趟排序還沒有結束，此時除節(jié)點87外，其余節(jié)點并不滿足大根堆的條件，所以需要對其余節(jié)點進行調整為大根堆。排序過程不再給出，Java和Python3的代碼實現如下。

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序數組序列
   * @return 排好序的數組序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 調整堆
   *
   * @param nums  待排序序列
   * @param parent   待調整根節(jié)點
   * @param length 數組序列長度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉樹節(jié)點i從編號1開始的左子節(jié)點位置在2i，此處數組下標從0開始，即左子節(jié)點所在數組索引位置為：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //節(jié)點有右子節(jié)點，且右子節(jié)點大于左子節(jié)點，則選取右子節(jié)點
      }
      if (temp > nums[childIndex]) {
        break; //如果選中節(jié)點大于其子節(jié)點，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //繼續(xù)向下調整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#調整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

以上這篇老生常談比較排序之堆排序就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: