- 堆排序--kuan -

堆排序

2007-04-12 晴

出处或者来源:课本

#include<iostream.h>

void Sift(float array[], int n, int i)//筛运算
{
int j;
float temp=array;

j=2*i+1;//array[j] 是　array　的左孩子
while(j <= n-1)//左孩子不空是循环
{
if(j < n-1 && array[j] < array[j+1])
j++; //右孩子比左孩子大　把　j 变成右孩子的下标

if(array[j] > temp)
{
array=array[j];//将array[j]调到双亲结点
i=j;//向下筛
j=2*i+1;
}
else
break;//temp最终位置找到
}
array=temp;
}

void HeapSort(float array[], int n) //时间O(nlog2n) 空间　O(1)
{
int i;
float temp;

for(i=n/2; i >= 0; i--)
Sift(array,n,i);//建立初始堆从最后的根结点开始　前向

for(i=1; i<=n-1; i++)
{
temp=array[0];//树根结点和当前区间最后一个结点对换
array[0]=array[n-i];
array[n-i]=temp;
Sift(array,n-i,0);// 筛array[0]结点，得到n－i　个结点的堆
}
}

void main()
{
int i,n;
cout<<"你输入几个数进行排序：";
cin>>n;
float *array=new float[n+1];
cout<<"请输入"<<n<<"个数："; //36 25 48 12 65 43 20 58
for(i=0; i<n; i++)
cin>>array;

HeapSort(array,n);

cout<<"排好序的数：";
for(i=0; i<n; i++)
cout<<array<<' ';
cout<<endl;
delete []array;
array=NULL;
}.

[全部]

# posted by kuan @ 2007-04-12 12:50:51 评论(0)

笔名：

评论：

最多1000字。当前字数：0
*

联系方式：