几种基本排序算法的实现

1、数据结构实验报告实验题目：几种根本排序算法的实现姓名：张耀班级：计嵌151学号：17实验目的实现直接插入排序,冒泡排序,简单项选择择排序,快速排序,希尔 排序,堆排序等 6 种常用内部排序算法,比拟各算法的比拟次数 和移动次数.二、数据结构设计(1) 设计待排序记录的存储结构.(2) 设计待排序数据的存储结构.(3) 输入：待排序数据的数据个数和数据可由键盘输入, 也可由程 序生成伪随机数,以菜单方式选择上述排序方法中的一个,并 指明输出第几趟排序的结果.(4) 输出：各趟排序结果或指定趟的排序结果, 以及对应的关键字 比拟次数和移动次数.三、算法设计与 N-S 图算法设计：编写一个主函数 m

2、ain() ,在主函数中设计一个简单的菜单,分别调用 6 种内部排序算法. 为了对各种排序算法的性能进行比拟, 算法中的主要工作是在算 法的适当位置插入对关键字的比拟次数和移动次数的计数操作.为 此,可设立一个实现排序算法中的关键字比拟的函数； 设立一个实现 排序算法中的关键字移动的函数； 设立一个实现排序算法中的关键字 交换的函数,从而解决比拟次数和移动次数的统计问题. 数据的输入也可以通过菜单项选择择输入方式： 键盘输入或由伪随机数程 序生成数据, 以便随时更换排序数据, 并根据不同要求对排序数据进 行排序,输出排序的结果以及对应的关键字比拟次数和移动次数. 对于测试数据,算法中可以考虑几

3、组数据的典型性,如正序,逆序和 不同程度等,以取得直观的感受,从而对不同算法进行比拟.四、程序清单#include<iostream> using namespace std;void showMenu()cout << "*菜单 *" << endl;cout << "1.直接插入排序" << endl;cout << "2.冒泡排序" << endl;cout << "3.简单项选择择排序" << end

4、l;cout << "4.快速排序" << endl;cout << "5.希尔排序" << endl;cout << "6.堆排序" << endl;cout << "7.退出程序" << endl;struct SqList int * key; int length;HeapAdjust(L, i, , compare_Time, move_Time);for (i = ; i>1; -i)value = 1

5、;1 = i;i = value;重新调整为大顶HeapAdjust(L, 1, i - 1, compare_Time, move_Time);.i-1 堆k+;cout << " 第 " << k << " 趟排序结果： " OutPut(L); cout << " 比拟次数为： " << compare_Time << endl; cout << " 移动次数为： " << move_Time << e

6、ndl;int main()int choice;SqList sq,sp;CreateSqList(sq);Copy(sq, sp);showMenu();cout << "Please enter your choice: " cin >> choice;while (choice != 0)void CreateSqList(SqList &sl).调整为大顶堆switch (choice)case 1:InsertSort(sq); cout << "最终结果：OutPut(sq); break;case 2:B

7、ubbleSort(sq); cout << "最终结果：OutPut(sq); break;case 3:SelectSort(sq); cout << "最终结果：OutPut(sq); break;case 4:QuitSort(sq); cout << "最终结果：OutPut(sq); break;case 5:int *p, n;cout << " 请输入增量个数：" << endl;cin >> n;p = new intn;cout << &qu

8、ot; 请输入各个增量的值： " << endl;for (int i = 0; i < n; i+)cin >> pi;ShellSort(sq, p, n); cout << "最终结果： "OutPut(sq); break;case 6:HeapSort(sq); cout <<最终结果:II.3OutPut(sq); break;case 7:cout << "程序运行结束,退出程序."<< en dl; retur n 0; break;Copy(sp,

9、sq);showMe nu();cout << "Please en ter your choice:"cin >> choice;return 0;五、运行与测试Q C. WI IND DWSsystem睛笛人数尿：4 2 5 7 18 3*菓单*1 亘接 S&AttJf 2启翹排呼3.閒单项选择弹排序 i.ftsSg 忙希誦序B.Wff 人退出裡序R- 8 7Please errter your choice； 1 第1尿排序站黑 2 第2超和受拮聚1 覇報命诈拮里：1 比拟次殖为：M 释动次隸为.8 最幽果；1*菜苣*1-0*人*佯2

10、冒泡排斤3 简車幺挥轴序 d.快速乘J?5 希不排斤6.OJ?7退岀程序PI ease enier your choice： 2壬錯栗-子结杲: 三序结来: 畦结果;'字结東: 三序结果: 比拟次数为,21 移动次数为：9 最终箱果z I第？超22111序 序* .堆 琳 "人- - - 1 1 1 1 4H 牯插拙选序程 r>:M:>:>:>:>:>: 卫接泡申赵$出ie鰭结结结结结结 t rnjhmT快希堆迟erltHbb序序库 bltlblfcL 卜|&>广 buL burbur 123 4 56 7 w*¥#

11、.az趙趙趙趙趙趙趟e 1 2 3 4 5 6 7.乙盲泡诽库3 简单项选择择排序4 快速樹5希尔廉序6 堆排序7退岀程序ce： 32222222'lease enier your chDice： 4 第趙排序結果： 第2超排佯结氣 翕3議件庄结氣 第乙越枠序结果 比拟吹数为：1 翔次数为,14 晶终结果：131112222514333 45533333 4153444 57 7 7 4 4 4 4 LO735 555 74447555 777 75 7377777 88CQ88877 88 8 8 8 8 CO335 5 7 885 5 5$t 喪7苗1.苣接神入排序氏閒甲隹择排序4 禹I排序5. 希尔排序6. J4# 序了 退出程序z,I ease enter your 亡 ho i ce ： 5mAflt个数:各个噌量的怪q 1第1髓排序结果：3J54287第2趟排序结為123457&比拟衣数为；15務动找稚为:3I 2 S 457 S2抽入排序 2卡泡排芋乩简单项选择择排仔4.快 iStlff &需尔 6.WJ? 厂退岀程序 lease enter your 悴稱排序结果： 跑嚇游结