堆排序

（1）定义顺序表的存储结构；

（2）在顺序表上实现堆排序；

（3）用大量的数据测试最好、最坏和平均情况下的排序速度。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
//定义顺序表的存储结构；
typedef struct {int key;//关键字项int otherinfo;//其他数据元素
}RedType;
typedef struct {RedType r[105];//r[0]闲置或用作哨兵单元int length;//顺序表表长
}SqList;//顺序表类型typedef SqList HeapType;void CreatSq(SqList &L) {printf("请输入数据个数：");scanf("%d", &L.length);printf("请输入%d个数据元素：", L.length);for (int i = 1; i <= L.length; i++)scanf("%d", &L.r[i].key);
}
void Print(SqList L) {printf("降序输出：");for (int i = 1; i <= L.length; i++)printf("%d ", L.r[i].key);printf("\n\n");
}void HeapAdjust(HeapType &H, int s, int m) {//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义//本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆RedType rc = H.r[s];for (int j = 2 * s; j <= m; j *= 2) {      //沿key较大的孩子节点向下筛选if (j < m && H.r[j].key >= H.r[j + 1].key) ++j;//j为key较大的记录的下标if (rc.key < H.r[j].key) break;        //rc应插入在位置s上H.r[s] = H.r[j];s = j;}H.r[s] = rc;                               //插入
}void HeapSort(HeapType &H) {//对顺序表H进行堆排序for (int i = H.length / 2; i > 0; i--)  //把H.r[1..H.length]建成大顶堆HeapAdjust(H, i, H.length);for (int i = H.length; i > 1; i--) {swap(H.r[1], H.r[i]);   //将堆顶记录和当前未经排序的子序列Hr[1..i]中最后一个记录相互交换HeapAdjust(H, 1, i - 1);//将H.r[1..i-1]重新调整为大顶堆}
}
int main()
{SqList L;printf("堆排序排序\n");CreatSq(L);HeapSort(L);Print(L);system("pause");return 0;
}