c語(yǔ)言中如何實(shí)現(xiàn)堆排序

這篇文章給大家介紹c語(yǔ)言中如何實(shí)現(xiàn)堆排序，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

堆是一棵順序存儲(chǔ)的完全二叉樹(shù)。
其中每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字，這樣的堆稱(chēng)為小根堆。
其中每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字，這樣的堆稱(chēng)為大根堆。
舉例來(lái)說(shuō)，對(duì)于n個(gè)元素的序列{R0, R1, … , Rn}當(dāng)且僅當(dāng)滿(mǎn)足下列關(guān)系之一時(shí)，稱(chēng)之為堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;

如上圖所示，序列R{3, 5, 8, 10, 7}是一個(gè)典型的小根堆。
堆中有兩個(gè)父結(jié)點(diǎn)，元素3和元素8。
元素3在數(shù)組中以R[0]表示，它的左孩子結(jié)點(diǎn)是R[1]，右孩子結(jié)點(diǎn)是R[2]。
元素5在數(shù)組中以R[1]表示，它的左孩子結(jié)點(diǎn)是R[3]，右孩子結(jié)點(diǎn)是R[4]，它的父結(jié)點(diǎn)是R[0]。可以看出，它們滿(mǎn)足以下規(guī)律：
設(shè)當(dāng)前元素在數(shù)組中以R[i]表示，那么，
(1) 它的左孩子結(jié)點(diǎn)是：R[2i+1];
(2) 它的右孩子結(jié)點(diǎn)是：R[2i+2];
(3) 它的父結(jié)點(diǎn)是：R[(i-1)/2];
(4) R[i] <= R[2i+1] 且 R[i] <= R[2i+2]。
首先，按堆的定義將數(shù)組R[0..n]調(diào)整為堆（這個(gè)過(guò)程稱(chēng)為創(chuàng)建初始堆），交換R[0]和R[n]；
然后，將R[0..n-1]調(diào)整為堆，交換R[0]和R[n-1]；
如此反復(fù)，直到交換了R[0]和R[1]為止。
以上思想可歸納為兩個(gè)操作：
（1）根據(jù)初始數(shù)組去構(gòu)造初始堆（構(gòu)建一個(gè)完全二叉樹(shù)，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）。
（2）每次交換第一個(gè)和最后一個(gè)元素，輸出最后一個(gè)元素（最大值），然后把剩下元素重新調(diào)整為大根堆。
當(dāng)輸出完最后一個(gè)元素后，這個(gè)數(shù)組已經(jīng)是按照從小到大的順序排列了。
先通過(guò)詳細(xì)的實(shí)例圖來(lái)看一下，如何構(gòu)建初始堆。
設(shè)有一個(gè)無(wú)序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

構(gòu)造了初始堆后，我們來(lái)看一下完整的堆排序處理：
還是針對(duì)前面提到的無(wú)序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來(lái)加以說(shuō)明。

相信，通過(guò)以上兩幅圖，應(yīng)該能很直觀的演示堆排序的操作處理。
代碼：

#include <stdio.h>
#include <windows.h>

void    HeapAdjust(int *array, int parent, int length);
void    printPart(int *array, int begin, int end);

int main()
{
    int array[10] = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
    int length = (sizeof(array) / sizeof(int));
    for (int i = length / 2 ; i >= 0; i--)
    {
        HeapAdjust(array, i, length);
    }
    for (int i = length - 1; i > 0; i--) 
    {
        // 最后一個(gè)元素和第一元素進(jìn)行交換
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        // 篩選 array[0] 結(jié)點(diǎn)，得到i-1個(gè)結(jié)點(diǎn)的堆
        HeapAdjust(array, 0, i);
        printf("第 %d 趟: \t", length - i);
        printPart(array, 0, length - 1);
    }
    system("pause");
    return 0;
}

void    HeapAdjust(int *array, int parent, int length)
{
    int tmp = array[parent];
    int Lchild = 2 * parent + 1;
    while (Lchild<length)
    {
        // 如果有右孩子結(jié)點(diǎn)，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)，則選取右孩子結(jié)點(diǎn)
        if (Lchild + 1 < length && array[Lchild] < array[Lchild + 1])
        {
            Lchild++;
        }

        // 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
        if (tmp >= array[Lchild])
            break;

        // 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
        array[parent] = array[Lchild];

        // 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選
        parent = Lchild;
        Lchild = 2 * Lchild + 1;
    }
    array[parent] = tmp;
}

void printPart(int *array, int begin, int end)
{
    for (int i = begin; i <= end; i++) 
    {
        printf("%d \t",array[i]);
    }
    printf("\n");
}

關(guān)于c語(yǔ)言中如何實(shí)現(xiàn)堆排序就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。