几种常见排序方法的比较.doc

重庆邮电大学移通学院计算机软件技术基础课程报告 题 目 几种常见排序方法的比较 姓 名 谢枞 学 号 0111100320 班 级 01111003 专 业 通信工程 2012年 6 月4日摘 要该程序是用C+语言实现的，在程序中随机生成N个数据，对这些数进行多种方法的排序，所用的这些排序方法都是在数据结构课中学习过的比如：插入排序、快速排序、冒泡排序等，而且还要对各个排序做出相应的比较。该演示程序以用户和计算机的对话方式执行，每次测试完毕，列表显示各种比较指标值。最后对结果作出了简单分析并将结果排序，包括对各组数据得出结果波动大小给予解析。关键字：插入排序、冒泡排序、比较的个数、改变的个数、所用的时间。目 录摘要目录1 问题描述11.1 题目内容11.2 基本要求11.3 测试数据12 需求分析22.1 输入输出的形式和输入值的范围22.2 程序所能达到的功能23 概要设计33.1 程序所需的抽象数据类型33.2 系统功能模块33.2.1 外部功能模块图 33.2.2 主函数功能模块图34 详细设计4 4.1 整个程序的流程图4 4.2 插入排序及其主要代码54.3 二路合并排序及其主要代码64.4 冒泡排序及其主要代码75 调试分析85.1 调试分析结果96 总结101问题描述1.1题目内容本演示程序对以下几种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、二路合并排序。主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序、逆序和不同程度的乱序。注意采用分块调试的方法。1.2基本要求1 待排序表的表长不小于100，其中数据要用的随机数产生程序产生，至少要用5组不同的输入数据体比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动）。2 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入待排序表的表长和不同的测试数据的数组，每次测试完毕，列表显示各种比较指标值。3最后对结果作出简单分析，包括对各组数据得出结果波动大小给予解析。1.3 测试数据由函数rand随机产生的数据。2 需求分析2.1输入输出的形式和输入值的范围 由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。程序输出的是对五种排序做的一些比较，即输出五种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。输入值的范围等价于程序中随机生成的数据的个数，即待排序表的表长不小于100，至少要用5组不同的输入数据体比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次的移动），在该程序中，随机生成的数据个数被初始化为了10000，数据越大就越容易比较。 2.2程序所能达到的功能输入N个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和用掉的时间。任意性：系统首先生成10000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间友好性：界面要友好，输入有提示，尽量展示人性化可读性：源程序代码清晰、有层次健壮性：用户输入非法数据时，系统要及时给出警告信息3 概要设计3.1程序所需的抽象数据类型typedef struct StudentData int num; /存放关键字，如零时变量，还有哨兵Data;typedef struct LinkListint Length; /存放随机数的个数Data RecordMAXSIZE;/用数组存放所有的随机数LinkList;3.2 系统功能模块3.2.1 主函数功能模块图主函数 main（）Display把数据写入文件Compare比较六种排序Show the menu显示主界面InitLinkList(LinkList* L)初始化链表set 定义或初始化变量 图 3.2.2 主函数功能模块图4.1 整个程序的流程图开始界面Compare 比较各排序二路合并排序冒泡排序插入排序比较各排序输出数据结束4.2 插入排序及其主要代码直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个纪录插入到已排好序的有序表中，从而得到一个新的、纪录数增1的有序表。例如，已知待排序的一组纪录的初始排列如下所示： R(49)、R(38)、R(65)、R(97)、R(76)、R(13)、R(27)、R(49) （4-1）假设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成一个含4个纪录的有序序列 R(38)、R(49)、R(65)、R(97) （4-2） 现要将式（4-1）中的第5个纪录插入上述序列，以得到一个新的含5个纪录的有序序列，则首先要在式（4-2）的序列中进行查找以确定R(76)、所应插入的位置，然后进行插入。假设从R(97)、起向左进行顺序查找，由于657697，则R(76)应插入在R(65)和R(97)之间，从而等到下列新的有序序列 R(38)、R(49)、R(65)、R(76)、R(97) （4-3）称从式（4-2）到（4-3）的过程为一趟直接插入排序。一般情况下，第i趟直接插入排序的操作为：在含有i-1个纪录的有序子序列r1.i-1中插入一个记录ri后，变成含有i个记录的有序子序列r1.i；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r0处设置监视哨。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。代码如下：void ShellSort(LinkList* L, int dlta, int t,int* CmpNum, int* ChgNum)int k;for (k=0; kt; k+)ShellInsert(L,dltak,CmpNum,ChgNum);void ShellInsert(LinkList* L,int dk, int* CmpNum, int* ChgNum)int i, j;Data Temp;for(i=dk; iLength;i+)if( LT(L-Recordi.num, L-Recordi-dk.num, CmpNum) )memcpy(&Temp,&L-Recordi,sizeof(Data);for(j=i-dk; j=0 & LT(Temp.num, L-Recordj.num, CmpNum) ; j-=dk) (*ChgNum)+;(*ChgNum)+;memcpy(&L-Recordj+dk,&L-Recordj,sizeof(Data);memcpy(&L-Recordj+dk,&Temp,sizeof(Data);4.3二路合并排序及其主要代码二路合并排序是另一类时间复杂度为O(nlog2n)的排序方法，它的基本思想是：将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到【n/2】个长度为2或1的有序子序列；再两两合并，直到得到一个长度为n的有序子序列时结束，如图所示。template void Merge(T A,int i1,int j1,int i2,int j2) / i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界T *Temp=new Tj2-i1+1; /分配能存放两个子序列的临时数组int i=i1,j=i2,k=0; /i,j是两个子序列的游动指针，k是Temp的游动指针 while (i=j1&j=j2) /若两个子序列都不空，则循环 if (Ai=Aj) Tempk+=Ai+; /将Ai和Aj中较小的存入Tempk else Tempk+=Aj+;while (i=j1) Tempk+=Ai+; /若第一个子序列中还有剩余的就存入Temp while (j=j2) Tempk+=Aj+; /若第二个子序列中还有剩余的就存入Temp for (i=0; ik; i+) Ai1+=Tempi; /将临时数组中的元素倒回A delete Temp; template void MergeSort(T A, int n) int i1,j1,i2,j2; /i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界 int size=1; /子序列中元素个数，初始化为1。 while (sizen) i1=0; while (i1+sizen) /若i1+sizen-1) j2=n-1; /若第2个子序列中不足size个元素，则置子序列2的上界j2=n-1 else j2=i2+size-1; /否则有size个，置j2=i2+size-1 Merge(A,i1,j1,i2,j2); /合并相邻两个子序列 i1=j2+1; /确定下一次合并第一个子序列的下界 size*=2; /元素个数扩大一倍 程序只将A数组中相邻的两个子序列（Ai1,Ai1+1,.,Aj1）和(Ai2,Ai2+1,.,Aj2)合并为一个子序列，其中i1、ji是子序列1在数组A中的下标，表示子序列的下、上界（i2j2）。由于两个子序列是相邻的，即j1+1=i2，因此它们中的元素总数为j2-i1+1。为实现上述两个子序列的合并，程序一开始就分配能存放两个子序列的临时数组（Temp0,Temp1,.,Tempj2-i1），用于保存合并的中间结果，本地合并结束后，再将临时数组中的元素“倒回”A中。4.4 冒泡排序及其主要算法冒泡排序（bubble sort）的过程很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。上述过程称做第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i趟冒泡排序是从L.r1到L.n-i+1依次比较相邻两个记录的关键字，并在“逆序”是交换相邻记录，其结果是这n-i+1个记录中关键字最大的纪录被交换到第n-i+1的位置上。整个冒泡排序过程需进行k（1=kn）趟，显然，判别冒泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum)int i,j;Data temp;for (i=0; iMAXSIZE-1;i+)for(j=0; jRecordj.num,L-Recordj+1.num,CmpNum)(*ChgNum)+;memcpy(&temp,&L-Recordj,sizeof(Data);memcpy(&L-Recordj,&L-Recordj+1,sizeof(Data);memcpy(&L-Recordj+1,&temp,sizeof(Data);6 总 结这次课程设计运用到了c+语言和数据结构知识点，课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力。这次课设使我了解我编程思想和编程技巧，也认识了软件生命周期的各个环境，包括构思、设计、编写、调试、发布、文档化、维护和修订。编程的风格也很重要，同学只关心程序运行的结果，而对程序代码的结构的良好丝毫不在意。这是非常不可取的，如果我们希望将来从事编程工作，在这一点上该引起足够的重视。这是严谨的态度，很重要！在写程序的过程中遇到的麻烦不是很多，由于课本上都把最基本的算法写的很清楚