C语言排序之 堆排序
时间：2022-11-21 08:27:01|栏目：C代码|点击： 次
前言：
堆是具有以下性质的完全二叉树
每个节点大于或等于其左右子节点，此时称为大顶（根）堆
?每个节点小于或等于其左右子节点，此时称为小顶（根）堆
完全二叉树在数组中下标换算公式
假设堆根节点从1开始编号（从1开始方便计算，0下标空着）
下面以编号为i的非根节点为例，计算其关联节点的下标公式为：
其父节点：i/2
其左孩子：2i
其右孩子：2i+1
注：把这个完全二叉树按层序遍历放入数组（0下标不用），则满足上面的关系表达
代码工作流程
整体流程
a. 根据节点换算公式先从最下层非叶节点开始，依次从右到左（自下而上）一直到根创建初始堆
b. 循环n-1次，依次执行：条件判断后交换堆顶和堆尾元素
重建除堆尾外元素为新堆，一直到根
重建堆函数流程
接收参数开始下标和数组有效长度
保存堆顶，自上而下建堆，如果堆顶（临时堆顶）比子节点小（大顶堆中），则孩子赋值给临时堆顶位置（不需要swap函数交换，swap没必要），并让临时堆顶位置指定子节点
for循环终止一定会找到合适的位置，此时临时堆顶指向的位置可能是函数调用时的位置，也可能发生改变（代码中执行了一次强制赋值）
大小顶堆使用场景
大顶堆用来做升序排序，小顶堆用来做降序排序
时间复杂度
O(nlogn)
不稳定
代码
#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
