堆排序法

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。

推薦度：

點(diǎn)擊下載本文 文檔為doc格式

導(dǎo)讀堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。

.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}

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

大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

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

1. 算法步驟

創(chuàng)建一個(gè)堆 H[0……n-1]；

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

把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置；

重復(fù)步驟 2，直到堆的尺寸為 1。

2. 動(dòng)圖演示

代碼實(shí)現(xiàn)JavaScript 實(shí)例 var len; ? ?// 因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長(zhǎng)度，所以把len設(shè)置成為全局變量function buildMaxHeap(arr) { ? // 建立大頂堆? ? len = arr.length;? ? for (var i = Math.floor(len/2); i >= 0; i--) {? ? ? ? heapify(arr, i);? ? }}function heapify(arr, i) { ? ? // 堆調(diào)整? ? 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實(shí)例 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實(shí)例 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實(shí)例 public class HeapSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容? ? ? ? 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 實(shí)例 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實(shí)例 #include #include void swap(int *a, int *b) {? ? int temp = *b;? ? *b = *a;? ? *a = temp;}void max_heapify(int arr[], int start, int end) {? ? // 建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)? ? int dad = start;? ? int son = dad * 2 + 1;? ? while (son <= end) { // 若子節(jié)點(diǎn)指標(biāo)在範(fàn)圍內(nèi)才做比較? ? ? ? if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的? ? ? ? ? ? son++;? ? ? ? if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)? ? ? ? ? ? return;? ? ? ? else { // 否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較? ? ? ? ? ? swap(&arr[dad], &arr[son]);? ? ? ? ? ? dad = son;? ? ? ? ? ? son = dad * 2 + 1;? ? ? ? }? ? }}void heap_sort(int arr[], int len) {? ? int i;? ? // 初始化，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整? ? for (i = len / 2 - 1; i >= 0; i--)? ? ? ? max_heapify(arr, i, len - 1);? ? // 先將第一個(gè)元素和已排好元素前一位做交換，再重新調(diào)整，直到排序完畢? ? 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++實(shí)例 #include #include using namespace std;void max_heapify(int arr[], int start, int end) {? ? // 建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)? ? int dad = start;? ? int son = dad * 2 + 1;? ? while (son <= end) { // 若子節(jié)點(diǎn)指標(biāo)在範(fàn)圍內(nèi)才做比較? ? ? ? if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的? ? ? ? ? ? son++;? ? ? ? if (arr[dad] > arr[son]) // 如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)? ? ? ? ? ? return;? ? ? ? else { // 否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較? ? ? ? ? ? swap(arr[dad], arr[son]);? ? ? ? ? ? dad = son;? ? ? ? ? ? son = dad * 2 + 1;? ? ? ? }? ? }}void heap_sort(int arr[], int len) {? ? // 初始化，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整? ? for (int i = len / 2 - 1; i >= 0; i--)? ? ? ? max_heapify(arr, i, len - 1);? ? // 先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再?gòu)男抡{(diào)整(剛調(diào)整的元素之前的元素)，直到排序完畢? ? 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

以下是熱心網(wǎng)友對(duì)堆排序算法的補(bǔ)充，僅供參考：

熱心網(wǎng)友提供的補(bǔ)充1：

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

/// 
/// 堆排序
/// 
/// 待排序數(shù)組
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];
    }
    // 初始數(shù)據(jù)建堆（從含最后一個(gè)結(jié)點(diǎn)的子樹開始構(gòu)建，依次向前，形成整個(gè)二叉堆）
    for (int i = vCount / 2; i >= 1; i--)
    {
        Restore(tempKey, i, vCount);
    }
    // 不斷輸出堆頂元素、重構(gòu)堆，進(jìn)行排序
    for (int i = vCount; i > 1; i--)
    {
        int temp = tempKey[i];
        tempKey[i] = tempKey[1];
        tempKey[1] = temp;
        Restore(tempKey, 1, i - 1);
    }
    //排序結(jié)果
    for (int i = 0; i < vCount; i++)
    {
        arr[i] = tempKey[i + 1];
    }
}
/// 
/// 二叉堆的重構(gòu)（針對(duì)于已構(gòu)建好的二叉堆首尾互換之后的重構(gòu)）
/// 
/// 
/// 根結(jié)點(diǎn)j
/// 結(jié)點(diǎn)數(shù)
static void Restore(int[] arr, int rootNode, int nodeCount)
{
    while (rootNode <= nodeCount / 2) // 保證根結(jié)點(diǎn)有子樹
    {
        //找出左右兒子的最大值
        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;
        }
    }
}

熱心網(wǎng)友提供的補(bǔ)充2：

堆排序是不穩(wěn)定的排序！

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

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

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

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

以上為堆排序算法詳細(xì)介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點(diǎn)，用一張圖概括：

關(guān)于時(shí)間復(fù)雜度

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

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

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

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

關(guān)于穩(wěn)定性

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數(shù)據(jù)規(guī)模

k："桶"的個(gè)數(shù)

In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

穩(wěn)定性：排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同

堆排序法

推薦度：

點(diǎn)擊下載本文 文檔為doc格式

為你推薦

資訊專欄

熱門視頻

相關(guān)推薦

科技

美食

生活

娛樂

健康

母嬰

教育

體育

更多

汽車

游戲

旅游

時(shí)尚

財(cái)經(jīng)

寵物

視頻號(hào)

抖音

快手

微博

首頁(yè)

電子數(shù)碼

互聯(lián)網(wǎng)

APP應(yīng)用

智能硬件

軟件測(cè)評(píng)

手機(jī)系統(tǒng)

5G/6G

科技百科

人工智能

堆排序法

堆排序法

堆排序法