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

内容发布更新时间 : 2025/5/21 16:35:02星期一 下面是文章的全部内容请认真阅读。

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

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. 总结

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

>>展开全文<<
12@gma联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi