排序算法――堆排序
來源：程序員人生 發布時間：2015-07-02 08:28:20 閱讀次數：2643次
關于堆排序的1些基本定義可參見我轉載的另外一篇博文。http://blog.csdn.net/u010275850/article/details/45311661
其實在學習堆的時候仔細的同學就能夠發現，只要順次保存刪除操作的數據，就能夠得到1個有序的序列。堆排序也是利用了這樣的思想。
算法實現：
/*根據最大堆實現的堆排序*/
#include<stdio.h>
#define LeftChild(i) (2*i+1)
void PercDown(int *data,int i,int n);
void Heapsort(int *data,int n);
void Swap(int *a,int *b);
int main()
{
int i=0;
int data[7]={97,53,26,41,59,31,58};
printf("Before Sort:
");
for(i=0;i<7;i++)
{
printf("%d ",data[i]);
}
Heapsort(data,7);
printf("
After Sort:
");
for(i=0;i<7;i++)
{
printf("%d ",data[i]);
}
return 0;
}
void PercDown(int *data,int i,int n)
{
int Child;
int tmp;
for(tmp=data[i];LeftChild(i)<n;i=Child)//i=Child其實相當于1個遞歸調用。相當于將大的孩子與父節點做了1次交換。交換以后繼續調劑
{ //LeftChild(i)<n表示調劑至葉節點為止
Child=LeftChild(i);
if((Child!=n⑴)&&(data[Child+1]>data[Child]))//取出大的孩子
Child++;
if(tmp<data[Child])//將大的孩子與父節點比較，父節點取大的值
data[i]=data[Child];//此時data[i]的值在tmp中還有1份拷貝，并未完全被覆蓋
else
break;
}
data[i]=tmp;//將tmp還給樹中適合位置
}
void Heapsort(int *data,int n)
{
int i;
for(i=n/2;i>=0;i--)//i=n/2表示從最后1個非葉節點開始調劑，（如果是葉節點，PercDown會跳過甚么都不做）i--則是此節點往前1次調劑非葉節點
PercDown(data,i,n);//i表示待調劑的父節點 n表示樹的節點數
for(i=n⑴;i>0;i--)
{
Swap(&data[0],&data[i]);
PercDown(data,0,i);
}
}
void Swap(int *a,int *b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
