北邮数据结构第四次实验题目一排序研讨.doc

北京邮电大学信息与通信工程学院 第 PAGE 14页 北京邮电大学电信工程学院 第 PAGE 1页 数据结构实验报告 实验名称： 实验四 排序（题目1） 姓 名： 班 级： 班内序号： 学 号： 1．实验要求 实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容：使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对2的结果进行分析，验证上述各种算法的时间复杂度。 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 程序采用的存储机构是顺序存储，如下图所示： a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7] 2.2 关键算法分析 2.2.1 插入排序 插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述过程如下： ①将待插入纪录赋值给哨兵r[0]：r[0]=r[i]; ②从后向前进行顺序查找：for(j=i-1;r[0]r[j];j--); ③元素后插：r[j+1]=r[j]; ④插入记录：r[j+1]=r[j]; void InsertSort(int r[],int n) { int comp=0; //比较次数计数器 int move=0; //移动次数计数器 for(int i=2;i=n;i++) { if(r[i]r[i-1]) { r[0]=r[i]; int j=i-1; for(;r[0]r[j];j--) //边查找，边后移 {r[j+1]=r[j];move++; comp++;} //循环中移动计数器++ comp++; //比较计数器++ r[j+1]=r[0];move++; //移动计数器++ } comp++; //比较计数器++ } cout本次直接插入排序数据长度为：n 移动：move次 比较：comp次endl; } 性能分析： 原序列正序时直接插入排序达到最好的时间性能，比较次数为n-1，移动次数为0。原序列逆序时直接插入排序达到最差时???性能，比较次数为，移动次数为。 直接插入排序的平均时间复杂度为，空间复杂度为。 直接插入排序是一种稳定的排序算法，特别适合于待排序集合基本有序的情况。 2.2.2 希尔排序 希尔排序的基本方法是将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。 希尔排序的整个过程如下： void ShellInsert(int r[],int n) { int comp=0; //比较次数计数器 int move=0; //移动次数计数器 for(int d=n/2;d=1;d=d/2) //以d为增量在子序列中进行插入排序 { for(int i=d+1;i=n;i++) //一趟希尔排序 { if(r[i]r[i-d]) { r[0]=r[i]; move++; //移动计数器++ int j=i-d; for(;j0r[0]r[j];j=j-d) //每隔d个记录，进行一次比较和移动，d=1时即是最后一趟直接插入排序 {r[j+d]=r[j];comp++;move++;} comp++; //比较计数器++ r[j+d]=r[0];move++; //移动计数器++ } comp++;//比较计数器++ } } cout本次希尔排序数据长度为：n 移动：move次 比较：comp次endl; } 希尔排序的时间复杂度在和之间，空间复杂度为，是一种不稳定的排序算法。 2.2.3 冒泡排序 冒泡排序的基本思想是，两两比较相邻的元素，如果反序，则交换位置，知道没有反序的元素为止。 具体描述如下： void BubbleSort(int r[],int n) { int comp=0; //比较次数计数器 int move=0;