堆排序。 #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)，且是一种稳定的排序算法。

相关问题

直接插入排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void InsertSort(SqList &L) { int i,j; for(i=2;i<=

L.length;i++) { //从第二个元素开始插入排序 　　　if(L.r[i].key<L.r[i-1].key) { 　　　　　L.r[0]=L.r[i]; //哨兵 　　　　　L.r[i]=L.r[i-1]; 　　　　　for(j=i-2;L.r[0].key<L.r[j].key;j--) { //从后往前比较 　　　　　　　L.r[j+1]=L.r[j]; //记录后移 　　　　　} 　　　　　L.r[j+1]=L.r[0]; //插入到正确位置 　　　} 　} }

以上是直接插入排序的 C++ 代码实现，使用了哨兵来简化代码。对于一个长度为n的序列，平均时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)，空间复杂度为O(1)。

#include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void SelectSort(SqList &L) { int i,j,k; ElemType t; for(i=1; ;++i) { k=i; for(j=i+1; ;++j) if( ) k=j; if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} } } 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; } int main() { SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); SelectSort(L); show(L); return 0; }

这是一个使用选择排序算法对输入的一组数据进行排序的 C++ 程序。程序中定义了一个结构体类型 ElemType，其中 key 表示关键字，otherinfo 表示其他信息。另外还定义了一个 SqList 结构体类型，其中 r 指向 ElemType 类型的数组，length 表示数组的长度。程序中定义了函数 SelectSort，用于实现选择排序算法；函数 Create_Sq 用于创建 SqList 类型的数据；函数 show 用于输出排序后的结果。程序的主函数中先创建 SqList 类型的数据，然后调用 SelectSort 函数对数据进行排序，最后调用 show 函数输出排序后的结果。