实验四题目1.doc

数据结构实验报告 实验名称： 实验四——题目一 学生姓名： 唐文旭 班 级：2013211118 班内序号： 09 学 号： 2013210524 日 期： 2015年1月5日 1．实验要求 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 2.2 关键算法分析 北京邮电大学信息与通信工程学院? 第2页? 希尔排序又称“缩小增量排序”，是对直接插入排序的一种改进，它利用了直接插入的两个特点：1.基本有序的序列，直接插入最快；2.记录个数很少的无序序列，直接插入也很快。希尔排序的基本思想为：将待排序的元素集分成多个子集，分别对这些子集进行直接插入排序，待整个序列基本有序时，再对元素进行一次直接插入排序。? 冒泡排序的基本思想是：两两比较相邻的元素，如果反序，则交换位置，直到没有反序的元素为止。具体的排序过程是：将整个待排序元素划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的元素；对无序区从前向后依次将相邻元素的关键码进行比较，若反序则交换，从而使得关键码小的元素向前移，关键码大的元素向后移；重复执行前一个步骤，直到无序区中没有反序的元素。? 快速排序元素的比较和移动是从两端向中间进行的。快速排序的基本思想是：在分区中选择一个元素作为轴值，将待排序元素划分成两个分区，使得左侧元素的关键码均小于或等于轴值，右侧元素的关键码均大于或等于轴值，然后分别对这两个分区重复上述过程，直到整个序列有序。? 简单选择排序的基本思想是：第1趟，在待排序记录r[1?n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2?n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟，在待排序记录r[i?n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。? r[0]留空，初始时赋为0? 2.2?关键算法分析? 1、直接插入排序? 自然语言描述：? （1）?将整个待排序的记录划分成有序区和无序区。有序区为待排序记录的第一个记录， 无序区为所有剩余带待排序记录。? （2）?从第二个数据开始依次插入到有序区中，直到所有记录插入完毕。?（3）?在r[0]处设置“哨兵”，记为要插入的记录r[i]，在自i-1起往前查找的过程中，同时 后移记录。? （4）?找到插入位置后，将待插入记录插入到有序表中。? （5）?重复执行（3）、（4），直到无序区中没有记录。? 伪代码描述：? ?初始化比较次数compare =0，移动次数move =0?2.?for(int?i=2;in;i++)?比较次数++? ?if(r[i]r[i-1设置哨兵r[0]=r[i]，移动次数++???????? ?for(j=i-1;r[0]r[j];j--) ?r[j+1]=r[j]?比较次数++；移动次数++；??????? ?r[j+1]=r[0]，移动次数++? 时间复杂度：最好情况下，待排序序列为正序，每趟秩序与有序序列的最后一个纪录的关键码比较一次，移动两次记录。总的比较次数为n-1，记录移动的次数为2（n-1）。因此，时间复杂度为O（n）。? 最坏情况下，待排序序列为逆序，比较次数为(n+2)(n+1)/2，移动次数为(n+4)(n-1)/2因此，时间复杂度为O（n2）.? 平均情况下，总的比较次数为n（n-1）/4，移动次数为（n+4）（n-1）/4，因此，时间复杂度为O（n2）? 2、希尔排序? 自然语言描述：? （1）?假设待排序记录为n个，先取整数dn，，将所有相距为d的记录构成一组，从而将整个待排序记录分为d个子序列。?（2）?对每个子序列分别进行直接插入排序。在每个子序列中，待插入记录和同一子序列 中的前一个记录比较，在插入记录r[i]时，自r[i-d]往前查找待插入位置，在查找过程中，记录后移也是移动d个位置。? （3）?当有哪些信誉好的足球投注网站位置j=0或者r[0]=r[j]，表示插入位置已经找到。在整个序列中，前d个记 录分别是d个子序列的第一个记录，所以从第d+1个记录开始插入。?（4）?再缩小d，重复以上步骤，再对每个子序列进行直接插入排序，直到d=1，即将所有 记录放在一组进行一