一、算法实现
堆排序算法的时间复杂度为O(nlgn),其算法实现如下:
void heap_sort(int *array, int max)
{
int idx = 0;
build_max_heap(array, max);
for(idx=max; idx>=2; idx--)
{
array[0] = array[1];
array[1] = array[idx];
array[idx] = array[0];
max_heapify(array, 1, idx-1);
}
}
/* 构建大头堆 */
void build_max_heap(int *array, int max)
{
int idx = max/2;
while(idx >= 1)
{
max_heapify(array, idx, max);
idx--;
}
}
void max_heapify(int *array, int idx, int max)
{
int left=LEFT(idx), right=RIGHT(idx), largest=-1;
if(left<=max && array[left]>array[idx])
{
largest = left;
}
else
{
largest = idx;
}
if(right<=max && array[right]>array[largest])
{
largest = right;
}
if(i != largest)
{
array[0] = array[idx]; /* 注:array[0]作为交换空间 */
array[idx] = array[largest];
array[largest] = array[0];
max_heapify(array, largest, max);
}
}
二、函数调用
#define ARRAY_NUM (11)
int main(int argc, char *argv[])
{
int idx = 0;
int array[ARRAY_NUM] = {-1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
heap_sort(array, ARRAY_NUM-1);
for(idx=1; idx<ARRAY_NUM; idx++)
{
fprintf(stdout, "array[%d]=%d\n", idx, array[idx]);
}
return 0;
}
分享到:
相关推荐
算法导论之堆排序,C语言实现版
算法导论上的堆排序c++源程序||学习分享
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
算法导论 源代码 C语言实现
算法导论C语言版本。下载后绝对不会后悔。嗯。谢谢
C语言的堆排序代码,堆排序是比较重要的一种算法,希望有用!
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
排序算法之堆排序【c语言版本】有注释,例子直接拿来演示即可,自行修改参数
自己做的 很辛苦的。堆排序课设的代码,用c语言做的 数据结构堆排序的算法演示~~~可以借鉴或 参考
算法导论 C语言各类算法
C语言版堆排序算法完成代码,欢迎交流讨论。
学习堆排序时自己编的代码,里面有自动生成随机数的代码段方便大家测试
算法导论 快速排序 堆排序 算法导论上的算法实现更加精简高效 代码可编译运行测试 加了测试用例 加了注释
参考《算法导论》这本书写的一个堆排序的代码,我个人是用Visual studio写的。只要一个积分哦
冒泡排序 简单选择排序 c语言基础 排序算法 数组操作 排序算法实验 简单的c语言程序 排序算法输出
算法导论 c语言的全部代码实现 需要c99的支持
实现算法导论中的堆排序,区别数组以0作为根,算法导论中的实现是以数组1作为根
算法导论是关于程序开发的一些算法与数据结构有关
根据算法导论书上的伪代码写的C语言版代码。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...