heapsort.txt

堆排序适合于待排序文件中记录较多的情况

//堆排序
#include<iostream.h>
#define max 50
typedef struct
{ int key;
 int data;
}recordtype;
void heapadjust(recordtype R[],int s,int t) //进行筛选的堆调整算法
{ int i,j;
 recordtype temp;
 temp=R[s];
 i=s;
 j=2*i;
 while(j<=t)
   { if((j<t)&&(R[j].key>R[j+1].key))
      j++;
    if(temp.key>R[j].key)
      { R[i]=R[j];
       i=j;
       j=2*i;
      }
    else
      j=t+1;  }
 R[i]=temp;
}
void heapsort(recordtype R[],int n) //对待排序文件R[]中的n个记录进行堆排序的算法
{ int i;
 recordtype temp;
 for(i=n/2;i>=1;i--)
   heapadjust(R,i,n);
 for(i=n;i>=1;i--)
   {temp=R[1];
    R[1]=R[i];
    R[i]=temp;
    heapadjust(R,1,i-1);   }
}
void main()
{ int i,n;
 cout<<"输入节点的个数:";
 cin>>n;
 recordtype R[max];
 cout<<"输入各个节点的数据:";
 for(i=1;i<=n;i++)
   cin>>R[i].key;
 for(i=1;i<=n;i++)
    heapsort(R,n);
 cout<<"结果为:";
 for(i=1;i<=n;i++)
   cout<<R[i].key<<" ";
 cout<<endl;
}