堆排序算法

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。以下是堆排序算法：

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間復雜度為 Ο(nlogn)。

1. 算法步驟

創建一個堆 H[0……n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；

重復步驟 2，直到堆的尺寸為 1。

2. 動圖演示

代碼實現JavaScript 實例 var len; ? ?// 因為聲明的多個函數都需要數據長度，所以把len設置成為全局變量function buildMaxHeap(arr) { ? // 建立大頂堆? ? len = arr.length;? ? for (var i = Math.floor(len/2); i >= 0; i--) {? ? ? ? heapify(arr, i);? ? }}function heapify(arr, i) { ? ? // 堆調整? ? var left = 2 * i + 1,? ? ? ? right = 2 * i + 2,? ? ? ? largest = i;? ? if (left < len && arr[left] > arr[largest]) {? ? ? ? largest = left;? ? }? ? if (right < len && arr[right] > arr[largest]) {? ? ? ? largest = right;? ? }? ? if (largest != i) {? ? ? ? swap(arr, i, largest);? ? ? ? heapify(arr, largest);? ? }}function swap(arr, i, j) {? ? var temp = arr[i];? ? arr[i] = arr[j];? ? arr[j] = temp;}function heapSort(arr) {? ? buildMaxHeap(arr);? ? for (var i = arr.length-1; i > 0; i--) {? ? ? ? swap(arr, 0, i);? ? ? ? len--;? ? ? ? heapify(arr, 0);? ? }? ? return arr;}Python實例 def buildMaxHeap(arr):? ? import math? ? for i in range(math.floor(len(arr)/2),-1,-1):? ? ? ? heapify(arr,i)def heapify(arr, i):? ? left = 2*i+1? ? right = 2*i+2? ? largest = i? ? if left < arrLen and arr[left] > arr[largest]:? ? ? ? largest = left? ? if right < arrLen and arr[right] > arr[largest]:? ? ? ? largest = right? ? if largest != i:? ? ? ? swap(arr, i, largest)? ? ? ? heapify(arr, largest)def swap(arr, i, j):? ? arr[i], arr[j] = arr[j], arr[i]def heapSort(arr):? ? global arrLen? ? arrLen = len(arr)? ? buildMaxHeap(arr)? ? for i in range(len(arr)-1,0,-1):? ? ? ? swap(arr,0,i)? ? ? ? arrLen -=1? ? ? ? heapify(arr, 0)? ? return arrGo實例 func heapSort(arr []int) []int {? ? ? ? arrLen := len(arr)? ? ? ? buildMaxHeap(arr, arrLen)? ? ? ? for i := arrLen - 1; i >= 0; i-- {? ? ? ? ? ? ? ? swap(arr, 0, i)? ? ? ? ? ? ? ? arrLen -= 1? ? ? ? ? ? ? ? heapify(arr, 0, arrLen)? ? ? ? }? ? ? ? return arr}func buildMaxHeap(arr []int, arrLen int) {? ? ? ? for i := arrLen / 2; i >= 0; i-- {? ? ? ? ? ? ? ? heapify(arr, i, arrLen)? ? ? ? }}func heapify(arr []int, i, arrLen int) {? ? ? ? left := 2*i + 1? ? ? ? right := 2*i + 2? ? ? ? largest := i? ? ? ? if left < arrLen && arr[left] > arr[largest] {? ? ? ? ? ? ? ? largest = left? ? ? ? }? ? ? ? if right < arrLen && arr[right] > arr[largest] {? ? ? ? ? ? ? ? largest = right? ? ? ? }? ? ? ? if largest != i {? ? ? ? ? ? ? ? swap(arr, i, largest)? ? ? ? ? ? ? ? heapify(arr, largest, arrLen)? ? ? ? }}func swap(arr []int, i, j int) {? ? ? ? arr[i], arr[j] = arr[j], arr[i]}Java實例 public class HeapSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝，不改變參數內容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? int len = arr.length;? ? ? ? buildMaxHeap(arr, len);? ? ? ? for (int i = len - 1; i > 0; i--) {? ? ? ? ? ? swap(arr, 0, i);? ? ? ? ? ? len--;? ? ? ? ? ? heapify(arr, 0, len);? ? ? ? }? ? ? ? return arr;? ? }? ? private void buildMaxHeap(int[] arr, int len) {? ? ? ? for (int i = (int) Math.floor(len / 2); i >= 0; i--) {? ? ? ? ? ? heapify(arr, i, len);? ? ? ? }? ? }? ? private void heapify(int[] arr, int i, int len) {? ? ? ? int left = 2 * i + 1;? ? ? ? int right = 2 * i + 2;? ? ? ? int largest = i;? ? ? ? if (left < len && arr[left] > arr[largest]) {? ? ? ? ? ? largest = left;? ? ? ? }? ? ? ? if (right < len && arr[right] > arr[largest]) {? ? ? ? ? ? largest = right;? ? ? ? }? ? ? ? if (largest != i) {? ? ? ? ? ? swap(arr, i, largest);? ? ? ? ? ? heapify(arr, largest, len);? ? ? ? }? ? }? ? private void swap(int[] arr, int i, int j) {? ? ? ? int temp = arr[i];? ? ? ? arr[i] = arr[j];? ? ? ? arr[j] = temp;? ? }}PHP 實例 function buildMaxHeap(&$arr){? ? global $len;? ? for ($i = floor($len/2); $i >= 0; $i--) {? ? ? ? heapify($arr, $i);? ? }}function heapify(&$arr, $i){? ? global $len;? ? $left = 2 * $i + 1;? ? $right = 2 * $i + 2;? ? $largest = $i;? ? if ($left < $len && $arr[$left] > $arr[$largest]) {? ? ? ? $largest = $left;? ? }? ? if ($right < $len && $arr[$right] > $arr[$largest]) {? ? ? ? $largest = $right;? ? }? ? if ($largest != $i) {? ? ? ? swap($arr, $i, $largest);? ? ? ? heapify($arr, $largest);? ? }}function swap(&$arr, $i, $j){? ? $temp = $arr[$i];? ? $arr[$i] = $arr[$j];? ? $arr[$j] = $temp;}function heapSort($arr) {? ? global $len;? ? $len = count($arr);? ? buildMaxHeap($arr);? ? for ($i = count($arr) - 1; $i > 0; $i--) {? ? ? ? swap($arr, 0, $i);? ? ? ? $len--;? ? ? ? heapify($arr, 0);? ? }? ? return $arr;}C實例 #include #include 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(" ");? ? return 0;}C++實例 #include #include 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;}

參考文章：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md

https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

以下是熱心網友對堆排序算法的補充，僅供參考：

熱心網友提供的補充1：

上方又沒些 C# 的堆排序，艾孜爾江補充如下：

/// 

/// 堆排序
/// 
/// 待排序數組
static void HeapSort(int[] arr)
{
    int vCount = arr.Length;
    int[] tempKey = new int[vCount + 1];
    // 元素索引從1開始
    for (int i = 0; i < vCount; i++)
    {
        tempKey[i + 1] = arr[i];
    }
    // 初始數據建堆（從含最后一個結點的子樹開始構建，依次向前，形成整個二叉堆）
    for (int i = vCount / 2; i >= 1; i--)
    {
        Restore(tempKey, i, vCount);
    }
    // 不斷輸出堆頂元素、重構堆，進行排序
    for (int i = vCount; i > 1; i--)
    {
        int temp = tempKey[i];
        tempKey[i] = tempKey[1];
        tempKey[1] = temp;
        Restore(tempKey, 1, i - 1);
    }
    //排序結果
    for (int i = 0; i < vCount; i++)
    {
        arr[i] = tempKey[i + 1];
    }
}
/// 

/// 二叉堆的重構（針對于已構建好的二叉堆首尾互換之后的重構）
/// 
/// 
/// 根結點j
/// 結點數
static void Restore(int[] arr, int rootNode, int nodeCount)
{
    while (rootNode <= nodeCount / 2) // 保證根結點有子樹
    {
        //找出左右兒子的最大值
        int m = (2 * rootNode + 1 <= nodeCount && arr[2 * rootNode + 1] > arr[2 * rootNode]) ? 2 * rootNode + 1 : 2 * rootNode;
        if (arr[m] > arr[rootNode])
        {
            int temp = arr[m];
            arr[m] = arr[rootNode];
            arr[rootNode] = temp;
            rootNode = m;
        }
        else
        {
            break;
        }
    }
}

熱心網友提供的補充2：

堆排序是不穩定的排序！

既然如此，每次構建大頂堆時，在 父節點、左子節點、右子節點取三者中最大者作為父節點就行。我們追尋的只是最終排序后的結果，所以可以簡化其中的步驟。

我將個人寫的 Java 代碼核心放在下方，有興趣的同學可以一起討論下：

public int[] sort(int a[]) {
    int len = a.length - 1;    
    for (int i = len; i > 0; i--) {
        maxHeap(a, i);        
        //交換 跟節點root 與 最后一個子節點i 的位置        
        swap(a, 0, i);        
        //i--無序數組尺寸減少了 
    }  
    return a;
}

/**構建一個大頂堆（完全二叉樹 ） 
* 從  最后一個非葉子節點  開始，若父節點小于子節點，則互換他們兩的位置。然后依次從右至左，從下到上進行！ 
* 最后一個非葉子節點，它的葉子節點 必定包括了最后一個（葉子）節點，所以 最后一個非葉子節點是 a[（n+1）/2-1] 
 
* @param a 
* @param lastIndex 這個數組的最后一個元素 
*/
static void maxHeap(int a[], int lastIndex) {
    for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
       //反正 堆排序不穩定，先比較父與左子，大則交換；與右子同理。（不care 左子與右子位置是否變了！） 
        if (i * 2 + 1 <= lastIndex && a[i] < a[i * 2 + 1]) {
            swap(a, i, i * 2 + 1);        
        }    
        if (i * 2 + 2 <= lastIndex && a[i] < a[i * 2 + 2]) {
            swap(a, i, i * 2 + 2);        
        }
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

以上為堆排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括：

關于時間復雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關于穩定性

穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：占用常數內存，不占用額外內存

Out-place：占用額外內存

穩定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同