北邮数据结构实验-排序报告

《北邮数据结构实验-排序报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：实验四--排序学生姓名：班级：班内序号：学号：日期：年月日1．实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数

2、测试线性表的正确性。2.程序分析程序主要分为两部分，第一部分是类：classSort,第二部分是main函数1.在类classSort中主要有以下几个成员构成公有成员：voidInsertSort(intr[],intn);//升序排列voidShellInsert(intr[],intn);//哈希排序voidBubbleSort(intr[],intn);//起泡排序voidQsort(intr[],inti,intj,intn);//快速排序voidSelectSort(intr[],intn);//简单选择排序voidHeapsort(intr[],intn);//堆

3、排序voidPrintsort(intch,intmove,intr[],intn);//打印私有成员：intPartion(intr[],intfirst,intend,intn,int&change,int&move);//快速排序voidSift(intr[],intk,intm,int&change,int&move);//小根堆筛选各个函数采用不同的方法进行排序2.在主函数main函数中1.定义三个数组a1正序数据，a2逆序数据，a3随机数据2.输入一个数d1d1=1时，对正序数据进行排序d1=2时，对逆序数据进行排序d1=3时，对随机数据进行排序3.定义一个类的对

4、象s，并通过s调用各个函数，并输出结果4.计算各个排序的函数进行排序所用的时间并打印2.1存储结构主要运用顺序表进行存储2.2关键算法分析1.直接插入排序算法：基本思想：设置r[0]为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r[0]插入算法分析：最好情况 正序序列：比较n-1移动0最坏情况 逆序序列：比较(2+n)*(n-1)/2移动 (4+n)*(n-1)/2平均情况 时间复杂度O(n2)空间复杂度O(1)2.希尔排序过程：设待排序对象序列有n个记录,先取d

5、。 然后缩小间隔d,例如取d=d/2，重复上述的子序列划分和排序工作。 直到最后取d=1,将所有对象放在同一个序列中排序为止分析时间复杂度 希尔排序的时间与“增量序列”有关，不同的“增量序列”时间复杂度不同。 经过大量的实验，时间复杂度 O(n2)和O(nlog2n)之间稳定性 希尔排序是一种不稳定的排序算法3.起泡排序具体过程 1）初始状态无序区为r[1..n] 2）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置pos。最后一次交换的位置pos，就是下一趟无序区r[1..pos] 3）反复执行2），直到无序区中没有反序的记录时间复杂度O(n2)空间复杂度

6、O(1)4.快速选择算法具体过程：①初始化 取第一个记录作为基准，保存在任意位置 i基准左侧待比较的记录，初始i=1 j基准右侧待比较的记录,初始j=n ②右侧扫描 从后向前找到第一个比基准小的记录，移至位置i ③左侧扫描 从前到后找到第一个比基准大的记录，移至位置j 反复执行②③，直到i=j结束，将r[0]移至r[i]。时间复杂度：O(n2)~~O(nlog2n)5.简单选择排序基本思想：第i趟排序在无序序列r[i..n]中选择关键码最小的记录，与r[i]交换，使有序序列不断增长直到全部排序完毕时间复杂度O(n2)空间复杂度O(1) 6.堆排序基本思想1：堆排序1）将待排序

7、的记录构造成一个堆 2）输出堆顶元素 3）将堆中最后一个元素移至堆顶，并将剩余元素调整成堆。 反复执行2)3)，直到堆中只有一个记录。基本思想2：构建堆 1）所有叶子结点都是堆 2）从n/2个记录(最后一个分支结点)开始筛选 3）直到根结点，结束 基本思想3：输出堆顶元素将堆顶元素和最后一个元素交换 如何将剩余元素调整成堆？ 1)需要输出堆顶元素n-1次 2)则第i次，需要调整的元素范围r[1..n-i] 3.程序运行结果开始输入d1输入是否正确d1=1=1d1=2d1=31正序数据逆序数据随机数据直接