duipaixu.c

用c++语言实现的堆排序算法 个人感觉不错仅供参考

#include	<iostream.h>
#define MAXSIZE  100
int length;
int pivotkey;
int pivotloc;
//Typedef  SqList  HeapType;   //堆采用顺序表存储表示

void HeapSort(int  *H) {  //对顺序表H进行堆排序
	void HeapAdjust (int *R, int s, int m);
	int i,t;
  for (i=length/2; i>0; --i)  //把H.r[1..H.Length]建成大堆顶
      HeapAdjust(H,i,length);
  for (i=length; i>1; --i) {
      t=H[1];H[1]=H[i]; H[i]=t;    //将堆顶记录和当前未经排序子序列
                     //H.r[1..i]中最后一个记录相互交换
      HeapAdjust(H,1,i-1);  //将H.r[1..i-1]重新调整为大堆顶
    }
}
void HeapAdjust (int *R, int s, int m)
{          // 已知 R[s..m]中记录的关键字除 R[s] 之外均
             // 满足堆的特征，本函数自上而下调整 R[s] 的
             // 关键字，使 R[s..m] 也成为一个大顶堆
int rc,j;
rc = R[s];                         // 暂存 R[s] 
for ( j=2*s; j<=m; j*=2 ) {  // j 初值指向左孩子
    if ( j<m && R[j]<R[j+1] )  ++j;     
                    // 左/右“子树根”之间先进行相互比较
                       // 令 j 指示关键字较大记录的位置
	if ( rc >= R[j] )  break; 
                     // 再作“根”和“子树根”之间的比较，
                       // 若“>=”成立，则说明已找到 rc 的插
                       // 入位置 s ，不需要继续往下调整
	R[s] = R[j];   s = j;    
                 // 否则记录上移，尚需继续往下调整
}
R[s] = rc;       // 将调整前的堆顶记录插入到 s 位置
} // HeapAdjust

void main(){
int a[MAXSIZE];
int i,n;
cout<<"请输入数组元素个数"<<endl;
cin>>n;
length=n;
cout<<"请输入数组元素的初值"<<endl;
for(i=1;i<=n;i++){
cin>>a[i];
}
//cout<<"请输入您想查找的元素"<<endl;
//cin>>type;
HeapSort(a);
cout<<"堆排序后数组元素的值是："<<endl;
for(i=1;i<=n;i++)
	cout<<a[i]<<"  ";
//if(i==0)cout<<"不能找到所给元素"<<endl;
//else cout<<"所给元素在数组中的位置是"<<i<<endl;
}