北京邮电大学信息与通信工程学院 第1页 数据结构实验报告 实验名称： 实验4——排序 学生姓名： 申宇飞 班 级： 2012211103 班内序号： 03 学 号： 2012210064 日 期： 2013 年 12 月 18 日 1．实验要求 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为 3 次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对 2 和 3 的结果进行分析，验证上述各种算法的时间复杂度 编写测试 main()函数测试线性表的正确性。 2. 程序分析 北京邮电大学信息与通信工程学院 第2页 （1）、设计一个菜单，格式如下： 1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出 （2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。 2.1 存储结构 2.2 关键算法分析 本程序包含了 9 个函数，它们分别是： （1）、直接插入排序的算法函数 InsertSort（）。 void InsertSort(SqList &L) { int i,j; for( i=2; i<=L.length;i++) { if(L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; L.r[i] = L.r[i-1]; for( j=i-2; (L.r[0].key < L.r[j].key); j--) L.r[j+1] = L.r[j]; L.r[j+1] = L.r[0]; } } } （2）、希尔排序的算法函数 ShellSort（）。 void ShellSort(SqList &L) { 北京邮电大学信息与通信工程学院 第3页 int i, j; int dk = 1;//增量 while(dk <=L.length/3) dk = 3*dk+1;//增大增量 while(dk>0) { dk /= 3;//减小增量 for (i = dk; i <=L.length; i++) { L.r[0].key = L.r[i].key; j = i; while ((j >= dk) && (L.r[j-dk].key > L.r[0].key)) { L.r[j].key = L.r[j-dk].key; j -= dk; } L.r[j].key = L.r[0].key; } } } （3）、冒泡排序算法函数 BubbleSort（）。 void BubbleSort(SqList &L) { int i,j; for(i=0;i
