北邮数据结构实验-排序报告.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.输入一个数d1 d1=1时，对正序数据进行排序 d1=2时，对逆序数据进行排序 d1=3时，对随机数据进行排序 3.定义一个类的对象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 n，比如d= n/2 作为间隔, 将全部对象分为 d 个子序列, 对每一个子序列中分别施行直接插入排序。 然后缩小间隔 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) 空间复杂度 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：