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

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

創(chuàng)新互聯(lián)建站網(wǎng)站建設服務商，為中小企業(yè)提供做網(wǎng)站、成都做網(wǎng)站服務，網(wǎng)站設計，網(wǎng)站改版維護等一站式綜合服務型公司，專業(yè)打造企業(yè)形象網(wǎng)站，讓您在眾多競爭對手中脫穎而出創(chuàng)新互聯(lián)建站。

堆是一棵順序存儲的完全二叉樹。
其中每個結點的關鍵字都不大于其孩子結點的關鍵字，這樣的堆稱為小根堆。
其中每個結點的關鍵字都不小于其孩子結點的關鍵字，這樣的堆稱為大根堆。
舉例來說，對于n個元素的序列{R0, R1, … , Rn}當且僅當滿足下列關系之一時，稱之為堆：
(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}是一個典型的小根堆。
堆中有兩個父結點，元素3和元素8。
元素3在數(shù)組中以R[0]表示，它的左孩子結點是R[1]，右孩子結點是R[2]。
元素5在數(shù)組中以R[1]表示，它的左孩子結點是R[3]，右孩子結點是R[4]，它的父結點是R[0]?？梢钥闯?，它們滿足以下規(guī)律：
設當前元素在數(shù)組中以R[i]表示，那么，
(1) 它的左孩子結點是：R[2i+1];
(2) 它的右孩子結點是：R[2i+2];
(3) 它的父結點是：R[(i-1)/2];
(4) R[i] <= R[2i+1] 且 R[i] <= R[2i+2]。
首先，按堆的定義將數(shù)組R[0..n]調整為堆（這個過程稱為創(chuàng)建初始堆），交換R[0]和R[n]；
然后，將R[0..n-1]調整為堆，交換R[0]和R[n-1]；
如此反復，直到交換了R[0]和R[1]為止。
以上思想可歸納為兩個操作：
（1）根據(jù)初始數(shù)組去構造初始堆（構建一個完全二叉樹，保證所有的父結點都比它的孩子結點數(shù)值大）。
（2）每次交換第一個和最后一個元素，輸出最后一個元素（最大值），然后把剩下元素重新調整為大根堆。
當輸出完最后一個元素后，這個數(shù)組已經(jīng)是按照從小到大的順序排列了。
先通過詳細的實例圖來看一下，如何構建初始堆。
設有一個無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

構造了初始堆后，我們來看一下完整的堆排序處理：
還是針對前面提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來加以說明。

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

#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--) 
    {
        // 最后一個元素和第一元素進行交換
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        // 篩選 array[0] 結點，得到i-1個結點的堆
        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)
    {
        // 如果有右孩子結點，并且右孩子結點的值大于左孩子結點，則選取右孩子結點
        if (Lchild + 1 < length && array[Lchild] < array[Lchild + 1])
        {
            Lchild++;
        }

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

        // 把孩子結點的值賦給父結點
        array[parent] = array[Lchild];

        // 選取孩子結點的左孩子結點,繼續(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");
}

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

當前題目：c語言中如何實現(xiàn)堆排序
轉載源于：http://bm7419.com/article18/igopgp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供域名注冊、網(wǎng)站內鏈、自適應網(wǎng)站、ChatGPT、網(wǎng)站策劃、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)