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

数据结构实验报告实验名称： 实验四-排序学生姓名： 班 级： 班内序号： 学 号： 日 期： 年月日1实验要求使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2. 程序分析 程序主要分为两部分，第一部分是类：class Sort,第二部分是main函数1.在类class Sort中 主要有以下几个成员构成 公有成员 ： void InsertSort(int r, int n); /升序排列void ShellInsert ( int r, int n);/哈希排序void BubbleSort ( int r, int n);/起泡排序void Qsort(int r, int i, int j,int n);/快速排序void SelectSort(int r, int n);/简单选择排序void Heapsort(int r,int n);/堆排序void Printsort(int ch,int move,int r,int n);/打印私有成员：int Partion(int r , int first, int end,int n,int &change,int &move);/快速排序void Sift (int r, int k, int m,int &change ,int &move);/小根堆筛选各个函数采用不同的方法进行排序2.在主函数main函数中1.定义三个数组a1正序数据 ，a2逆序数据 ，a3随机数据2.输入一个数d1d1=1时，对正序数据进行排序d1=2时，对逆序数据进行排序d1=3时，对随机数据进行排序3.定义一个类的对象s，并通过s调用各个函数，并输出结果4.计算各个排序的函数进行排序所用的时间并打印2.1 存储结构主要运用顺序表进行存储2.2 关键算法分析1.直接插入排序算法：基本思想：设置r0为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r0插入算法分析：最好情况正序序列：比较n-1 移动 0最坏情况逆序序列：比较(2+n)*(n-1)/2移动(4+n)*(n-1)/2平均情况时间复杂度O(n2) 空间复杂度O(1)2.希尔排序过程：设待排序对象序列有 n 个记录,先取 d n，比如d= n/2 作为间隔, 将全部对象分为 d 个子序列, 对每一个子序列中分别施行直接插入排序。然后缩小间隔 d, 例如取 d =d/2，重复上述的子序列划分和排序工作。直到最后取 d = 1, 将所有对象放在同一个序列中排序为止分析时间复杂度希尔排序的时间与“增量序列”有关，不同的“增量序列”时间复杂度不同。经过大量的实验，时间复杂度O(n2) 和 O(nlog2n) 之间稳定性 希尔排序是一种不稳定的排序算法3.起泡排序具体过程1）初始状态无序区为r1.n2）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置pos。最后一次交换的位置pos，就是下一趟无序区r1.pos3）反复执行2），直到无序区中没有反序的记录时间复杂度 O(n2) 空间复杂度 O(1)4.快速选择算法具体过程： 初始化 取第一个记录作为基准，保存在任意位置 i 基准左侧待比较的记录， 初始i=1 j 基准右侧待比较的记录, 初始j=n 右侧扫描 从后向前找到第一个比基准小的记录，移至位置i 左侧扫描 从前到后找到第一个比基准大的记录，移至位置j 反复执行，直到i=j结束，将r0移至ri。时间复杂度：O(n2) O(nlog2n)5.简单选择排序基本思想：第 i 趟排序在无序序列ri.n 中选择关键码最小的记录，与ri交换，使有序序列不断增长直到全部排序完毕时间复杂度 O(n2) 空间复杂度O(1)6.堆排序基本思想1：堆排序1）将待排序的记录构造成一个堆2）输出堆顶元素3）将堆中最后一个元素移至堆顶，并将剩余元素调整成堆。反复执行2) 3)，直到堆中只有一个记录。基本思想2：构建堆 1）所有叶子结点都是堆 2）从n/2个记录(最后一个分支结点)开始筛选 3）直到根结点，结束基本思想3：输出堆顶元素将堆顶元素和最后一个元素交换如何将剩余元素调整成堆？1)需要输出堆顶元素n-1次2)则第i次，需要调整的元素范围r1.n-i3. 程序运行结果 开始输入d1输入是否正确d1=1=1d1=2d1=31正序数据逆序数据随机数据直接插入排序哈希排序快速排序起泡排序堆排序简单选择排序计时开始计时结束输出结果统计移动和交换次数结束是4. 总结在做这个程序的时候，曾遇到很多困扰的地方,各种修改。我觉得这次实验是一次有趣的体验。既让我感