圖解排序算法-堆排序（附源碼）
時間：2021-08-19 16:27:59
手機看文章
掃描二維碼
隨時隨地手機看文章
[導讀]01—認識堆排序堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，它的最好、最好、平均復雜度都為nlog(n)，它也是不穩(wěn)定排序算法。堆是具有以下性質的完全二叉樹：每個結點的值都大于等于其左右孩子結點的值，稱為最大堆。每個結點的值都小于等于其左右孩子結點的值，稱為最小堆。如下圖：0...
01—認識堆排序
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，它的最好、最好、平均復雜度都為nlog(n)，它也是不穩(wěn)定排序算法。堆是具有以下性質的完全二叉樹：每個結點的值都大于等于其左右孩子結點的值，稱為最大堆。每個結點的值都小于等于其左右孩子結點的值，稱為最小堆。如下圖：
02—堆排序思想及其實現(xiàn)無論網(wǎng)上還是書本上介紹堆排序的實現(xiàn)都是用數(shù)組實現(xiàn)，但是今天我們用二叉樹的思想實現(xiàn)堆排序。堆排序思想：將待排序列構造成一個最小堆，此時整個序列的最小值就是堆的根結點，新結點插入都將從左子樹開始填充到右子樹，新插入的結點先成為葉子結點，再從新插入的結點開始往上遍歷，如果父結點的值比該結點的值大則交換數(shù)據(jù)，直到父結點的值比其結點的值小為止。重復對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);堆結點里的高度并不是二叉樹的高度，由于二叉堆是完全二叉樹，因此只要結點的左右子樹不是滿二叉樹且高度不一致時，就可繼續(xù)插入結點，直到左右子樹都是滿二叉樹且高度一致，再往下一層插入結點。新建堆結點函數(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;
}釋放堆結點函數(shù)實現(xiàn)：
if(node == NULL){
????????return;
????}
????node->left = NULL;
????node->right = NULL;
????free(node);
}二叉堆插入結點步驟：將新插入的結點按照層級結構成為葉子結點，再從新結點往根結點遍歷，如果其父結點的值比該結點的值小，則交換數(shù)據(jù)，這個過程稱為上濾。新插入的結點不斷上濾，直到父結點的值比其結點的值小則停止上濾。如圖所示：
交換數(shù)據(jù)函數(shù)實現(xiàn)：
void?swap(int?*a, int?*b){
????int?c = *a;
????*a = *b;
????*b = c;
}上濾操作函數(shù)實現(xiàn)：
tree_node_t *up_filter(tree_node_t *root){
????if(root == NULL){
????????return?NULL;
????}
????if(root->left != NULL? 
下載文檔
