堆排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void HeapAdjust(SqList &L,int s,int m) { ElemType rc; int j; rc=L.r[s]; for(j=2*s;j<=m; j*=2 ) { if( j ) ++j; if( rc.key>=L.r[j].key ) break; L.r[s]=L.r[j]; s=j; } L.r[s]=rc; } void Create_Sq(SqList &L) { int i,n; cin>>n; //输入的值不大于 MAXSIZE for(i=1;i<=n;i++) { cin>>L.r[i].key; L.length++; } } void show(SqList L) { int i; for(i=1;i<=L.length;i++) if(i==1) cout<<L.r[i].key; else cout<<" "<<L.r[i].key; } //把无序序列L.r[1..n]建成大根堆 void CreatHeap(SqList &L) { int i,n; n=L.length; for(i=n/2;i>0;--i) HeapAdjust(L,i,n); } void HeapSort(SqList &L) { int i; ElemType x; CreatHeap(L); for( i=L.length;i>1;--i ) { x=L.r[1]; L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust( L,1,i-1 ); } } int main() { SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); HeapSort(L); show(L); return 0; } 输入样例： 第一行输入一个数n(输入的值不大于 MAXSIZE)。 第二行依次输入n个数 9 30 45 53 78 65 9 12 17 23 输出样例： 输出升序排列的结果。 9 12 17 23 30 45 53 65 78

堆排序是一种基于完全二叉树结构的排序算法，它的核心思想是将待排序的数组看作是一棵完全二叉树，并将其转换为一个大顶堆或小顶堆。通过不断将根节点与最后一个节点交换，并重新构建大顶堆或小顶堆的方式来完成排序。它的时间复杂度为O(nlogn)，且是一种稳定的排序算法。