C语言排序之 堆排序

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

到此这篇关于C语言排序之 堆排序的文章就介绍到这了,更多相关C语言排序内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    金蝶凭证排序号乱了

    金蝶凭证排序号乱了,,1.金蝶的顺序号跟凭证号不一致怎么办没关系的,可以在凭证过滤界面选择按凭证号或者凭证顺序号来排序,一般都选择凭证号

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    cad怎么设置节点|CAD怎么加节点

    cad怎么设置节点|CAD怎么加节点,,1. CAD怎么加节点天正CAD软件画节点的方法:1、在打开的软件中点击左侧工具栏中的图块图案-通用图库。2、

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    上下标快捷键|上下标快捷键怎么打

    上下标快捷键|上下标快捷键怎么打,,上下标快捷键怎么打上标快捷键:首先,选中需要加上标的字符,然后使用Word快捷键“ Ctrl + Shift + (加号)+

    word图标排序快捷键|word的快捷图标

    word图标排序快捷键|word的快捷图标,,1. word的快捷图标1、大家说的都是如何打开word,而不是像建空白文件夹那样,因为没有直接新建空白word

    下标快捷键ps|下标快捷键快

    下标快捷键ps|下标快捷键快,,下标快捷键快word下标快捷键怎么用方法/步骤:1.双击打开需要使用快捷键输入下标的word文档。2.选定需要下标

    海龙节点快捷键|海龙工具快捷键

    海龙节点快捷键|海龙工具快捷键,,1. 海龙工具快捷键惠普笔记本电脑的优点:1、 品牌:这年头买任何东西都要涉及这样一个问题,很多人购买东西都