堆排序（第6章）

本文主要是介绍堆排序（第6章），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据《算法导论》第6章堆排序算法编写，程序可运行。

#include <STDIO.H>#include <STDLIB.H>
#include <MATH.H>/*求父节点的下标*/
int PARENT(int i)
{
double a=i/2.0;
return (int)ceil(a)-1; 
}/*求左孩子的下标*/
int LEFT(int i)
{
return 2*i+1;
}/*求右孩子的下标*/
int RIGHT(int i)
{
return 2*i+2;
}/*********************************************************  函数名: void MAX_HEAPIFY(int A[],int heap_size,int i)*  函数功能:维护堆的最大堆的性质.heap_size为对中元素的个数.*  输入参数:int A[],int heap_size,int i*  输出参数:void*  附加说明:以LEFT(i)和RIGHT(i)为根节点的二叉树均为最大堆，现在使i为根节点的二叉树也为最大堆.*  作者:YL*  当前版本: v_1*  完成日期: 2014-04-22 
/********************************************************/
void MAX_HEAPIFY(int A[],int heap_size,int i)
{
int l,r,largest,exchange;
l=LEFT(i);
r=RIGHT(i);
if (l<heap_size&&A[l]>A[i])
largest=l;
else
largest=i;
if(r<heap_size&&A[r]>A[largest])
largest=r;if (largest!=i){
exchange=A[i];
A[i]=A[largest];
A[largest]=exchange;
MAX_HEAPIFY(A,heap_size,largest);}
}/*********************************************************  函数名: void BUILD_MAX_HEAP(int A[],int heap_size)*  函数功能:将一个无序的数组创建成一个最大堆.*  输入参数:int A[],int heap_size*  输出参数:void*  附加说明:*  作者:YL*  当前版本: v_1*  完成日期: 2014-04-22 
/********************************************************/
void BUILD_MAX_HEAP(int A[],int heap_size)
{
int i;
for(i=heap_size/2-1;i>=0;i--)
MAX_HEAPIFY(A,heap_size,i);
}/*********************************************************  函数名: void HEAPSORT(int A[],int heap_size)*  函数功能:将一个无序的数组从小到大排序.*  输入参数:int A[],int heap_size*  输出参数:void*  附加说明:*  作者:YL*  当前版本: v_1*  完成日期: 2014-04-23 
/********************************************************/
void HEAPSORT(int A[],int heap_size)
{int i,exchange;BUILD_MAX_HEAP(A,heap_size);
for (i=heap_size-1;i>=1;i--)
{
exchange=A[0];
A[0]=A[i];
A[i]=exchange;
heap_size=heap_size-1;
MAX_HEAPIFY(A,heap_size,0);
}
}

这篇关于堆排序（第6章）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---