算法导论 c语言,算法导论 之 堆排序[C语言]
一、算法实现
堆排序算法的时间复杂度为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(idx != 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
{
fprintf(stdout, "array[%d]=%d\n", idx, array[idx]);
}
return 0;
}
总结
以上是生活随笔为你收集整理的算法导论 c语言,算法导论 之 堆排序[C语言]的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： c语言行计数程序,C语言非常简单的字符统
- 下一篇： c调用易语言串口,易语言串口API源码