C語言排序之?堆排序

更新時間：2022年04月19日 10:44:16 作者：sndapk

這篇文章主要介紹了C語言排序之堆排序，文章基于C語言的相關(guān)資料展開詳細(xì)內(nèi)容，具有一定的參考資料，需要的小伙伴可以參考一下

前言：

堆是具有以下性質(zhì)的完全二叉樹

每個節(jié)點大于或等于其左右子節(jié)點，此時稱為大頂（根）堆

?每個節(jié)點小于或等于其左右子節(jié)點，此時稱為小頂（根）堆

完全二叉樹在數(shù)組中下標(biāo)換算公式

假設(shè)堆根節(jié)點從1開始編號（從1開始方便計算，0下標(biāo)空著）
下面以編號為i的非根節(jié)點為例，計算其關(guān)聯(lián)節(jié)點的下標(biāo)公式為：
其父節(jié)點：i/2
其左孩子：2i
其右孩子：2i+1

注：把這個完全二叉樹按層序遍歷放入數(shù)組（0下標(biāo)不用），則滿足上面的關(guān)系表達

代碼工作流程

整體流程

a. 根據(jù)節(jié)點換算公式先從最下層非葉節(jié)點開始，依次從右到左（自下而上）一直到根創(chuàng)建初始堆

b. 循環(huán)n-1次，依次執(zhí)行：條件判斷后交換堆頂和堆尾元素
重建除堆尾外元素為新堆，一直到根

重建堆函數(shù)流程

接收參數(shù)開始下標(biāo)和數(shù)組有效長度
保存堆頂，自上而下建堆，如果堆頂（臨時堆頂）比子節(jié)點?。ù箜敹阎校?，則孩子賦值給臨時堆頂位置（不需要swap函數(shù)交換，swap沒必要），并讓臨時堆頂位置指定子節(jié)點
for循環(huán)終止一定會找到合適的位置，此時臨時堆頂指向的位置可能是函數(shù)調(diào)用時的位置，也可能發(fā)生改變（代碼中執(zhí)行了一次強制賦值）

大小頂堆使用場景

大頂堆用來做升序排序，小頂堆用來做降序排序

時間復(fù)雜度

O(nlogn)
不穩(wěn)定

代碼

#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 9

typedef struct {
    int r[MAXSIZE+1]; // first index used as tmp, not real data
    int len;
}SqList;

void swap(SqList *L, int i, int j) {
    int tmp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = tmp;
}


void heap_adjust(SqList *L, int s, int len) {
    int temp, i;

    temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust

    for (i=s*2; i<=len; i*=2) { // compare with child
        if (i<len && L->r[i] < L->r[i+1]) {
            i++; // select the max child
        }

        if (temp >= L->r[i]) {
            break; // need not adjust
        }

        L->r[s] = L->r[i]; //need not swap, because always use temp compare with next level child

        s = i; // next loop, now s sub tree root node may be a invalid element
    }

    L->r[s] = temp; // finally, must be found the right place(or not changed)

}


void heap_adjust_2(SqList *L, int s, int len) {
    printf("use test function\n");
    int temp, i;

    temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust

    for (i=s*2; i<=len; i*=2) { // compare with child
        if (i<len && L->r[i] < L->r[i+1]) {
            i++; // select the max child
        }

        if (temp >= L->r[i]) {
            break; // need not adjust
        }

        swap(L, s, i); //need not swap, because always use temp compare with next level child

        s = i; // next loop, now s sub tree root node may be a invalid element
    }

    L->r[s] = temp; // finally, must be found the right place(or not changed)

}

void heap_sort(SqList *L) {
    // init serial to a heap first(type: big top), down->up and right->left
    int i, j;
    for (i=L->len/2; i>0; --i) {
        heap_adjust(L, i, L->len);
        //heap_adjust_2(L, i, L->len);
    }


    for (j=L->len; j>1; --j) {
        swap(L, 1, j);
        heap_adjust(L, 1, j-1);
    }

}

int main(void) {
    SqList list = {
        {999,50,10,90,30,70,40,80,60,20},
        MAXSIZE
    };

    heap_sort(&list);
    printf("after heap_sort:\n");
    for (int i=0; i<=MAXSIZE; i++) {
        printf("index: %d, value: %d\n",i,list.r[i]);
    }
    return 0;
}

output

? c gcc sort_heap.c && ./a.out
after heap_sort:
index: 0, value: 999
index: 1, value: 10
index: 2, value: 20
index: 3, value: 30
index: 4, value: 40
index: 5, value: 50
index: 6, value: 60
index: 7, value: 70
index: 8, value: 80
index: 9, value: 90

到此這篇關(guān)于C語言排序之堆排序的文章就介紹到這了,更多相關(guān)C語言排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: