《数据结构实验八》由会员分享，可在线阅读，更多相关《数据结构实验八（1页珍藏版）》请在金锄头文库上搜索。
1、实验八 内排序算法比较本实验目的是使读者，掌握常用排序方法的基本思想，通过实验加深理解各种排序算法，通过实 验掌握各种排序方法的时间复杂度分析，了解各种排序方法的优缺点及适用范围。1排序算法的实现(设计性实验)【问题描述】 排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素 的任意序列重新排列成一个按键有序的序列。【基本要求】1. 产生系统菜单，菜单项如下：1 退出2 产生随机数3 使用直接插入排序算法进行排序4 使用折半插入排序算法进行排序5 使用冒泡排序算法进行排序6 使用简单选择排序算法进行排序7 打印数组内容(或输出内容到文件)2. 随机产生n个整数(
2、大小范围：09999),将其存于数组A0.n-1中。n可由用户输入，测试时为n赋值100、200、300、1 000和2 000及更多。调用相应的算法进行排序，然后输出。【选做要求】1. 在以上基础实现堆排序和快速排序算法。2. 对各个算法进行实验比较，计算出平均比较次数c、平均移动次数m。c和m由总比较次数nn n n和总移动次数除以个数n所得。3. 对实验结果数据进行对比分析。(n可从100,200,1000,2000,10000, 20000逐步增加)【测试数据】产生随机数的算法可参考如下：需包含以下两个头文件iomanip和time.hint num;int * arr = new int _num:srand (tins i gned) t ime (NULL);for (int i=0 ; Knum; i+):arri二rand()%10000;for (int i=0; iXimm; i+):coutserw(7)arriif (i%10 = 9) con巳ndl;
