堆排序

堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

基本介紹

• 中文名：堆排序
• 外文名：Heapsort
• 類別：排序算法
• 發明人：羅伯特·弗洛伊德
• 起源於：羅伯特·弗洛伊德

簡介

堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆的操作

在堆的數據結構中，堆中的最大值總是位於根節點（在優先佇列中使用堆的話堆中的最小值位於根節點）。堆中定義以下幾種操作：

• 最大堆調整（Max Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
• 創建最大堆（Build Max Heap）：將堆中的所有數據重新排序
• 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞歸運算

實現示例

C語言

#include <stdio.h>#include <stdlib.h>void swap(int* a, int* b) {    int temp = *b;    *b = *a;    *a = temp;}void max_heapify(int arr[], int start, int end) {    //建立父節點指標和子節點指標    int dad = start;    int son = dad * 2 + 1;    while (son <= end) { //若子節點指標在範圍內才做比較        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的            son++;        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函式            return;        else { //否則交換父子內容再繼續子節點和孫節點比較            swap(&arr[dad], &arr[son]);            dad = son;            son = dad * 2 + 1;        }    }}void heap_sort(int arr[], int len) {    int i;    //初始化，i從最後一個父節點開始調整    for (i = len / 2 - 1; i >= 0; i--)        max_heapify(arr, i, len - 1);    //先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢    for (i = len - 1; i > 0; i--) {        swap(&arr[0], &arr[i]);        max_heapify(arr, 0, i - 1);    }}int main() {    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };    int len = (int) sizeof(arr) / sizeof(*arr);    heap_sort(arr, len);    int i;    for (i = 0; i < len; i++)        printf("%d ", arr[i]);    printf("\n");    return 0;}

C++

#include <iostream>#include <algorithm>using namespace std;void max_heapify(int arr[], int start, int end) {    //建立父節點指標和子節點指標    int dad = start;    int son = dad * 2 + 1;    while (son <= end) { //若子節點指標在範圍內才做比較        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的            son++;        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函式            return;        else { //否則交換父子內容再繼續子節點和孫節點比較            swap(arr[dad], arr[son]);            dad = son;            son = dad * 2 + 1;        }    }}void heap_sort(int arr[], int len) {    //初始化，i從最後一個父節點開始調整    for (int i = len / 2 - 1; i >= 0; i--)        max_heapify(arr, i, len - 1);    //先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢    for (int i = len - 1; i > 0; i--) {        swap(arr[0], arr[i]);        max_heapify(arr, 0, i - 1);    }}int main() {    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };    int len = (int) sizeof(arr) / sizeof(*arr);    heap_sort(arr, len);    for (int i = 0; i < len; i++)        cout << arr[i] << ' ';    cout << endl;    return 0;}

Python語言

def big_endian(arr, start, end):   root = start   while True:       child = root * 2 + 1   # 左孩子       if child > end:        # 孩子比最後一個節點還大 也就意味著最後一個葉子節點了 就得跳出去一次循環已經調整完畢           break       if child + 1 <= end and arr[child] < arr[child + 1]:   # 為了始終讓其跟子元素的較大值比較 如果右邊大就左換右，左邊大的話就默認           child += 1       if arr[root] < arr[child]:     # 父節點小於子節點直接換位置 同時坐標也得換這樣下次循環可以準確判斷是否為最底層是不是調整完畢           arr[root], arr[child] = arr[child], arr[root]           root = child       else:                            # 父子節點順序正常 直接過           break                      def heap_sort(arr):   # 無序區大根堆排序   first = len(arr) // 2 - 1   for start in range(first, -1, -1):   # 從下到上，從右到左對每個節點進調整 循環得到非葉子節點       big_endian(arr, start, len(arr) - 1)  # 去調整所有的節點   for end in range(len(arr) - 1, 0, -1):       arr[0], arr[end] = arr[end], arr[0]   # 頂部尾部互換位置       big_endian(arr, 0, end - 1)          # 重新調整子節點的順序  從頂開始調整   return arr      def main():   l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]   print(heap_sort(l))  # 原地排序   if __name__ == "__main__":   main()