圖解排序算法-堆排序（附源碼）
時(shí)間：2021-08-19 16:27:59
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]01—認(rèn)識(shí)堆排序堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，它的最好、最好、平均復(fù)雜度都為nlog(n)，它也是不穩(wěn)定排序算法。堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都大于等于其左右孩子結(jié)點(diǎn)的值，稱為最大堆。每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值，稱為最小堆。如下圖：0...
01—認(rèn)識(shí)堆排序
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，它的最好、最好、平均復(fù)雜度都為nlog(n)，它也是不穩(wěn)定排序算法。堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都大于等于其左右孩子結(jié)點(diǎn)的值，稱為最大堆。每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值，稱為最小堆。如下圖：
02—堆排序思想及其實(shí)現(xiàn)無(wú)論網(wǎng)上還是書(shū)本上介紹堆排序的實(shí)現(xiàn)都是用數(shù)組實(shí)現(xiàn)，但是今天我們用二叉樹(shù)的思想實(shí)現(xiàn)堆排序。堆排序思想：將待排序列構(gòu)造成一個(gè)最小堆，此時(shí)整個(gè)序列的最小值就是堆的根結(jié)點(diǎn)，新結(jié)點(diǎn)插入都將從左子樹(shù)開(kāi)始填充到右子樹(shù)，新插入的結(jié)點(diǎn)先成為葉子結(jié)點(diǎn)，再?gòu)男虏迦氲慕Y(jié)點(diǎn)開(kāi)始往上遍歷，如果父結(jié)點(diǎn)的值比該結(jié)點(diǎn)的值大則交換數(shù)據(jù)，直到父結(jié)點(diǎn)的值比其結(jié)點(diǎn)的值小為止。重復(fù)對(duì)n個(gè)值進(jìn)行操作，依次取出根結(jié)點(diǎn)，則整個(gè)序列是有序的。定義堆結(jié)點(diǎn)和聲明操作函數(shù)：
#define?INT_NAN (0xFFFFFFFF - 1)
typedef?struct?tree_node{
????struct?tree_node?*left;
????struct?tree_node?*right;
????int?data;
????int?height;
}tree_node_t;
extern?tree_node_t *new_tree_node(int?data);
extern?int?heap_sort_get_node(tree_node_t?**root);
extern?void?heap_sort_insert_node(tree_node_t?**root, int?data);
extern?void?destroy_heap_tree(tree_node_t?*root);
extern?void?tree_print(tree_node_t?*root);堆結(jié)點(diǎn)里的高度并不是二叉樹(shù)的高度，由于二叉堆是完全二叉樹(shù)，因此只要結(jié)點(diǎn)的左右子樹(shù)不是滿二叉樹(shù)且高度不一致時(shí)，就可繼續(xù)插入結(jié)點(diǎn)，直到左右子樹(shù)都是滿二叉樹(shù)且高度一致，再往下一層插入結(jié)點(diǎn)。新建堆結(jié)點(diǎn)函數(shù)實(shí)現(xiàn)：
tree_node_t?*new_tree_node(int?data){
????tree_node_t?*node = malloc(sizeof(tree_node_t));
????if(node == NULL){
????????return?NULL;
????}
????node->data = data;
????node->left = NULL;
????node->right = NULL;
????node->height = 1;
????return?node;
}釋放堆結(jié)點(diǎn)函數(shù)實(shí)現(xiàn)：
if(node == NULL){
????????return;
????}
????node->left = NULL;
????node->right = NULL;
????free(node);
}二叉堆插入結(jié)點(diǎn)步驟：將新插入的結(jié)點(diǎn)按照層級(jí)結(jié)構(gòu)成為葉子結(jié)點(diǎn)，再?gòu)男陆Y(jié)點(diǎn)往根結(jié)點(diǎn)遍歷，如果其父結(jié)點(diǎn)的值比該結(jié)點(diǎn)的值小，則交換數(shù)據(jù)，這個(gè)過(guò)程稱為上濾。新插入的結(jié)點(diǎn)不斷上濾，直到父結(jié)點(diǎn)的值比其結(jié)點(diǎn)的值小則停止上濾。如圖所示：
交換數(shù)據(jù)函數(shù)實(shí)現(xiàn)：
void?swap(int?*a, int?*b){
????int?c = *a;
????*a = *b;
????*b = c;
}上濾操作函數(shù)實(shí)現(xiàn)：
tree_node_t *up_filter(tree_node_t *root){
????if(root == NULL){
????????return?NULL;
????}
????if(root->left != NULL? 
下載文檔
