北邮数据结构实验报告实验四排序含源码

北京邮电大学信息与通信工程学院

for(j=2*s; j<=m; j*=2) {

//沿着结点记录较小的向下筛选 if(j

if(rc.key>= H.r[j].key) break;

H.r[s] = H.r[j]; s = j; }

H.r[s] = rc; }

void HeapSort(HeapType &H) { int i;

RedType temp;

for(i = H.length; i>0; --i) HeapAdjust(H,i,H.length); for(i=H.length; i>1; --i) {

temp = H.r[1]; H.r[1] = H.r[i]; H.r[i] = temp;

HeapAdjust(H,1,i-1); } （7）、对存储数字的遍历函数Visit（）、初始化函数InitSqList（）。 void Visit(SqList L) {

for(int i=1; i<=L.length; i++) cout<

void InitSqList(SqList &L,int a[]) {

for(int i=1;i<=L.length;i++) L.r[i].key = a[i]; } （8）、主函数main（）。 关键算法的时间、空间复杂度：

排序法 平均时间 最差情形 稳定度 额外空间 备注

冒泡 O(n2) O(n2) 稳定 O(1) n小时较好 交换 O(n2) O(n2) 不稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好

插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好

第5页

北京邮电大学信息与通信工程学院

Shell O(nlogn) O(ns) 1

2.3 其他

3. 程序运行结果

主函数流程： 直接插入希尔排序 排序 ShellSort() InsertSort() 主函数main 初始化随机数组 冒泡排序 BubbleSort() 快速排序 Qsort() 堆排序 HeapSort()

第6页

北京邮电大学信息与通信工程学院

第7页

北京邮电大学信息与通信工程学院

4. 总结

首先，对程序的设计缺少优化，本次程序需要运行之后手动进行输入数据，以后可以尝试把数据改为在源代码中输入，这样就可以运行之后马上显示数据，这样就避免了相同数据的重复输入。

此外，生成数组函数及本程序中的代码有的采用了递归形式，如果考虑用栈来模拟的话，效率会有提升，所以运行时间还和代码的实现有关。

本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题，得不到实现。后来对算法进行改进，最终把问题得以解决。而且以后可以试着去写一段可以计算出时间的函数。

代码

#include #include #include using namespace std;

int i,j,temp,k;//设置全局变量

long double GetNowTime() //取系统时间 { LARGE_INTEGER litmp; LONG64 QPart; QueryPerformanceCounter(&litmp); QPart=litmp.QuadPart; return (long double)QPart; }

第8页