堆排序

本頁面將簡要介紹堆排序。

定義

堆排序（英語：Heapsort）是指利用二叉堆這種數據結構所設計的一種排序算法。堆排序的適用數據結構為數組。

過程

堆排序的本質是建立在堆上的選擇排序。

排序

首先建立大頂堆，然後將堆頂的元素取出，作為最大值，與數組尾部的元素交換，並維持殘餘堆的性質；

之後將堆頂的元素取出，作為次大值，與數組倒數第二位元素交換，並維持殘餘堆的性質；

以此類推，在第 \(n-1\) 次操作後，整個數組就完成了排序。

在數組上建立二叉堆

從根節點開始，依次將每一層的節點排列在數組裏。

於是有數組中下標為 i 的節點，對應的父結點、左子結點和右子結點如下：

iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

性質

穩定性

同選擇排序一樣，由於其中交換位置的操作，所以是不穩定的排序算法。

時間複雜度

堆排序的最優時間複雜度、平均時間複雜度、最壞時間複雜度均為 \(O(n\log n)\)。

空間複雜度

由於可以在輸入數組上建立堆，所以這是一個原地算法。

實現

C++Python

void sift_down(int arr[], int start, int end) {
  // 計算父結點和子結點的下標
  int parent = start;
  int child = parent * 2 + 1;
  while (child <= end) {  // 子結點下標在範圍內才做比較
    // 先比較兩個子結點大小，選擇最大的
    if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
    // 如果父結點比子結點大，代表調整完畢，直接跳出函數
    if (arr[parent] >= arr[child])
      return;
    else {  // 否則交換父子內容，子結點再和孫結點比較
      swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // 從最後一個節點的父節點開始 sift down 以完成堆化 (heapify)
  for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
  // 先將第一個元素和已經排好的元素前一位做交換，再重新調整（剛調整的元素之前的元素），直到排序完畢
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    sift_down(arr, 0, i - 1);
  }
}

def sift_down(arr, start, end):
    # 計算父結點和子結點的下標
    parent = int(start)
    child = int(parent * 2 + 1)
    while child <= end: # 子結點下標在範圍內才做比較
        # 先比較兩個子結點大小，選擇最大的
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        # 如果父結點比子結點大，代表調整完畢，直接跳出函數
        if arr[parent] >= arr[child]:
            return
        else: # 否則交換父子內容，子結點再和孫結點比較
            arr[parent], arr[child] = arr[child], arr[parent]
            parent = child
            child = int(parent * 2 + 1)

def heap_sort(arr, len):
  # 從最後一個節點的父節點開始 sift down 以完成堆化 (heapify)
    i = (len - 1 - 1) / 2
    while(i >= 0):
        sift_down(arr, i, len - 1)
        i -= 1
  # 先將第一個元素和已經排好的元素前一位做交換，再重新調整（剛調整的元素之前的元素），直到排序完畢
    i = len - 1
    while(i > 0):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, 0, i - 1)
        i -= 1

外部鏈接

堆排序 - 維基百科，自由的百科全書

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用