南邮数据结构上机实验四内排序算法的实现以及性能比较

1、 实验报告 课程名称 （2015/2016学年 第二学期） 数据结构A 实验名称 内排序算法的实现以及性能比较 实验时间 2016 年 5 月 26 日 指导单位 计算机科学与技术系 指导教师 骆健 学生姓名 耿宙 班级学号 B14111615 学院係） 管理学院专 业信息管理与信息系统 2 卅 E貝U )2 Ht afUtil0- nF* * 实习题名：内排序算法的实现及性能比较 班级B141116姓名 耿宙 学号 B14111615 日期2016. 05. 26 问题描述 验证教材的齐种内排序算法，分析齐种排序算法的时间复杂度；改进教材中的快速 排序算法，使得当子集合小于10个元素师改用宜

2、接插入排序；使用随即数发生器产生 大数拯集合，运行上述齐排序算法，使用系统时钟测量各算法所需的实际时间，并进行 比较。系统时钟包含在头文件“time.h中。 概要设计 文件Sgt. cpp中包括了简单选择排序SelectSort 0 直接插入排序InsertSort () 冒泡排序BubbleSort ()两路合并排序Merge()快速排序Quicksort ()以及改进的快 速排序GQuickSortO六个内排序算法函数。主主函数main的代码如下图所示: Ul vM| t WB I h III Utinh uMnh tl|Ah HMOk 爼I:肚 I 負-vis f toy b 祁协F B

3、H心“ 0 详细设计 1. 类和类的层次设计 在此次程序的设讣中没有进行类的定义。程序的主要设讣是使用齐种内排序算法对随机 生成的数列进行排列，并进行性能的比较除此之外还对快速排序进行了改进。下图为主函 数main的流程图: 欢迎下载 I c bck.zarcfwuUi; c 2utgiy ： i卄 C6Ut-*ndl; S * rturaO; mainO 2. 核心算法 1）简单选择排序: 简单选择排序的基本思想是：第1趟，在待排序记录r1-rn冲选出垠小的记录，将它与 r交换；第2趟，在待排序记录r2l-rn冲选出最小的记录，将它与交换：以此类推, 第i趟在待排序记录riHrn中选出最小的

4、记录，将它与ri交换，使有序序列不断增长直到 全部排序完毕。 2）直接插入排序: 插入排序的思想是将组无序的元素分别插入一个已经有序的的数组里.并保证插入后的数组 也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组nl-r为初 始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0）,则nl默认为 只有一个元素的有序数组，n2插入只有nl构成的有序数组中，则此时有序数组的元素数量 变为2。以此类推，到第1个元素时，前个元素己经是有序的，此时只需将第1个元素插 入到有序数组中并使之保持有序。如此宜至最后一个元素插入完毕，整个插入拙序完成。 3冒泡排序: 冒泡排序每

5、遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次人的元素放到数组 倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡拙序完成。 4）快速排序: 快速扌4序是采用了分而治之的思想.但与合并排序有所不同的是快速排序先“工作”（这里是 分割或partition）,再递归。快速排序的主要思想是保证数组前半部分小于后半部分的元素, 然后分别对前半部分和后半部分再分别进行排序.直至所有元素有序。 5）两路合并排序 两路合并排序算法的基本思想是：将待扌旧芋元素平分成大小人致相同的两个了序列，然后对每 个子序列分别使用递归的方法进行两路合并排序.直到了序列长度变为1，最后利用合并算法 将得到的

6、己拙序好的两个了序列合并成个有序的序列。两路介井排序算法的核心部分是将子 问题的解组合成原问题解得合并操作。常用的操作是新建个序列序列的大小等于耍合并的 两个子序列的长度之和。比较两个了序列中的最小值，输出其中较小者到新建的序列中.重复 此过程宜到其中一个了序列为空。如果另一个了序列中还有元素未输出，则将剩余元素依次输 出到新建序列中即可.最终得到一个有序序列。 此外还对快速排序进行了改进，改进算法流程图如下所示: GQuickSort () 四. 程序代码 改进的快速排序 icmp late void GQuickSort(T A(ljni n) GQSort(AAn-l): icmp la

7、te void GQSorl(T Ajnt leftJnt right) int ij; if(right=9) j=right+l; do do i+;while (A(il6 52 *7 k 27 *2 29 / 69 创 29 27 K 84 * 兀 76 tt 71 73 23 F 44 22 M 26 49 6S 鈿 frt 73 S 76 K 04 22 41 W 12 21 4 21 宀 M 4 n n 41 M K(1 70 Gi 2 39 M n 32 u Gt I? $ tt n u 也)i i 73 Td 17 il 60 23 Z1 K V? IT 54 i3 191

8、$5 1 M SB U 31 i $2 1167*9319g717 Id 79 M 51 1) 64 S 3S 414S92? *4 I l M30m54614764$ 64 , 9 a 76 2$ 69 3 7B*7ttd7t :f M 34 H 32 74 74 4* 1 M 79 37 f ZS It 65 tS 76 (4 8V 3 ；M 33028075)“64鉛 29 74 71 4 64 616421S)7S a=b; b=teinp; icmp laie void SelectSort(T Aunt n) 简单选择排序 int small; for(int i=O:ifAljA

9、smaIl) small: Swap(A(i,A(smalll): icmp laie void InsertSortd AJnt n)/宜接插入排序 for(int i=l:i0 while(i0) lasl=0: for(j=0:ji:j+) if(AU+nAU) Swap(Arjl，A|j+lJ): lasi=j: i=Iast; icmp lale void QuickSortd Aunt n)快速排序 QSort(AAn-l); templaie void QSort(T A(jni leftjnt right) int i j: ifleftAEIeft): Swap(A(i,A|

10、j); while(ij): Swap(Alefl.Ajl); QSort(AJeftJ-l): QSort( A j+bright)： icmp laie void GQuickSorUT Ajnt n) 改进的快速排序 GQSort(A.O.n-l); icmp laie void GQSorifT Aunt lefldnt right) int i j; if(righl=9) i=left: j=righl+l; do do i+;while (AiAleft): if(ij) Swap(A(iJ,A|j3): while(ij): Swap(A|lefl,Atj)； QSort(AJ

11、eftJ-l): QSort( A j+bright)： else InsertSort(Ajight-left+1); return; icmp lale void MergefT AEJjnt i bint j I ant i2.ini j2)两路合并排序 T* Temp=new Tfj2-i 1+1： int i=il J=i2.k=O: while(i=j 1 else Tempk+=Aj+; while (i=jl ) Tempk 卄=Ai 卄; while(j=j2) Tempk 卄=Aj +; for(i=0：ik:i+) Ail+=Tempil； de 一 etc 二 Temp

12、- -emp 虫 CAC-ass TV woid Mcrgcsort(T Asm n) int 二 JLi2J2- iiU size= wh=c(sizcAn) ig whi一c (二+sizc:n) i2il+siza j正2三 if(i2+sizclvni T- C 一 SC j2Hi2+sizc一八 Mcrgc(A二 Ji2j2= 二 Hj2 二 J sizcf 2- c 一 ocks 一 art. finish 八 srand(=mc(NULL)r in【3H3S- iiU *aHncw in二nK in【*b=newm二nk in【薛new亘nk iiu *dHnewm二nk iiU

13、 *CHncw in二n一八 ini *fHncw in二nk colkaq崙辛豪弔空讶.AACndr for(in 二=oxcn=+) coluAAa 三八d, b三盘三 c三点m d三点m Nv”持续时间 Nv”持续时间 coutendl: siart=clock(); SeleclSort(a.n): cout经过简单选择排序后的序列为:endl; fori=0:in:i+) coutai ”； coutendl: finish=clock(); couivv”开始时间为:“vvslartvv “vv”结束时间为:finish* 为:(double)(finish start)/ CLO

14、CKS_PER_SECendl; siart=clock(); InsertSort(b.n)： coiK”经过直接插入排序后的序列为:endl; for(i=0;in:i+) coutbfij couivvcndl: finish=clock(); couivv”开始时间为:“vvsiartvv “vv“结朿时间为:“vvfinishvT 为:(double)(finish - start)/ CLOCKS_PER_SECendl; siart=clock(); BubblcSort(cm); cout经过冒泡排序后的序列为:cndl; for(i=0：in:i+) coutci ”； co

15、utendl: finish=clock(); couivv”开始时间为:“vvsiartvv “vv“结朿时间为:“vvCinishvv“ 为:(double)(finish - start)/ CLOCKS_PER_SECendl; siart=clock(); QuickSortdn); cout过快速排序后的序列为:cndl; for(i=0：in:i+) coutd(i ”； coutendl: finish=clock(): couivv”开始时间为:“vvslartvv “vv”结束时间为:finish* 为:(double)(finish start)/ CLOCKS_PER_SECendl; siart=clock(); MergeSort(e.n); cout经过两路合并排序后的序列为:endl; for(i=0;in:i+) coutei ”； couivvcndl: finish=clock(); couivv”开始时间为:“vvsiartvv “VV”结朿时间为:“vvfinishvv“持续时间 为:(double)(finish - st