排序算法的比较

排序算法的比较1课程设计名称排序算法的比较概述排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。内部排序算法主要分为5大类，有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。2使用工具软件MicrosoftVisualC++6.03课程设计内容简介3.1课程设计内容掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核比较他们之间的优劣。3.2基本要求1.任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间2.友好性：界面要友好，输入有提示，尽量展示人性化3.可读性：源程序代码清晰、有层次4.健壮性：用户输入非法数据时，系统要及时给出警告信息3.3课程设计思想程序设计的总体思路：首先构建main()函数，根据题目的要求，再分别构建四个排序函数：冒泡排序函数（longBubblesort(longR[],longn)）、选择排序函数（longselectsort(longR[],longn)）、直接插入排序函数（longinsertsort(longR[],longn)）和快速排序函数（voidQuickSort(longR[],longn)）。为了使程序具有可读性和层次感，建立一个导航函数（voidDaoHang()）和操作函数（voidoperate(longa[],longn)），其中，voidDaoHang()用来告知用户程序的操作流程，voidoperate(longa[],longn)用来接收用户不同的选择，从而调用其它函数。3.4程序分析3.4.1存储结构顺序存储结构（如图1）示意图a0a1a2a3a4图13.4.2关键算法分析关键算法1实现四种算法的基本排序功能1．冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。实现过程（如图2）。对于数组（2125491608）。初态：2125491608第一趟：2125160849第二趟：2116082549第三趟：1608212549第四趟：0816212549图22．选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。实现过程（如图3）。对于数组（2125491608）。初态：2125491608第一趟：0825491621第二趟：0816492521第三趟：0816212549图33．直接插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。实现过程（如图4）。对于数组（2125491608）。初态：2125491608第一趟：2125491608第二趟：2125491608第三趟：2125491608第四趟：1621254908第五趟：0816212549图44．快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。实现过程（如图5）对于数组（2125491608）。初态：R[0]=212125491608low第一趟：R[0]=210825491608lowR[0]=21R[0]=21lowR[0]=21R[0]=210825491625081649162508164916250816494925lowhighhighlowhighhighhighR[0]=21low=high图5关键算法二获取当前系统时间，精确到毫秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。//以冒泡排序为例start=(double)clock();//开始Bubblesort(R,n);end=(double)clock();//结束Time=(double)(end-start)/CLK_TCK;//相减，精确到毫秒关键算法三：实现手动与计算机随机双重输入。手动输入检查程序的正确性，计算机随即输入，可以比较各排序算法的性能。voidRand()//随机数函数voidHandInput()//手动输入函数关键算法四纠错功能。在用户输入非法数据时，给予警告，并要求用户重新输入，不必重启程序。3.4.3时间复杂度与空间复杂度：理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：0816214925排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)lowhigh图63.4.4选择排序算法的依据影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下4点：待排序的记录数目n的大小。记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。关键字的结构及其分布情况。对排序稳定性的要求。起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)简单选择排序O(n2)O(n2)O(n2)O(1)3.5程序流程图图7输入0输入a输入排序方法输入错误输入错误判断手动还是随机输入(1,2)?HandInput()(手动输入)1Rand();(随机输入)2voidDaoHang()voidoperate()cina[i];//数据存储选择排序方法Voidprint()结束main()3.6运行环境MicrosoftVisualC++6.0/WIN32ConsoleApplication3.7运行结果3.7.1当手动输入五个数据时，运行结果（如图8）图83.7.2当选择随机数时，运行结果(如图9)图93.8得意之处得意之处1将时间精确到毫秒，使得实验结果更容易观察比较。代码如下（冒泡排序为例）：start=(double)clock();degree=Bubblesort(R,n);end=(double)clock();Time=(double)(end-start)/;其中CLK_TCK值为1000，即将时间精确到毫秒（图10）。图10得意之处2将排序过程的每一趟输出，并且将已排好序的用中括号括起来，这样以来，可以直接看出排序过程是否正确以及深入了解排序过程的每一步。如：对于冒泡排序（图11）图11得意之处3冒泡排序算法中，运用做标记的方法，使得排序得到正确结果后，便停止做不必要的循环。代码如下while(i1){longlastExchangeIndex=1;//表示已经有序for(longj=1;ji;j++)if(R[j+1]R[j]){longt=R[j];R[j]=R[j+1];R[j+1]=t;BT++;lastExchangeIndex=j;//记下进行的位置}i=lastExchangeIndex;//本趟进行过交换的最后一个记录的位置}4课程设计中目前存在问题1．交换次数统计不够精确。2．无论时间还是移动次数，应该有一个对比结果，不能只是罗列出来。3．对于快速排序，存在两个问题。其一，不能两边同时进行排序，使得排序趟数增加；其二，没能格式化输出，使得输出不清晰，不美观。5自我感受1．在初期构思代码的时候，首先构造了各种算法的基本实现代码，已经能够实现四种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生函数，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达四种排序算法的简单调用和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。调用精确的系统函数实现时间的统计。此外还添加了一系列优化，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。2．程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。3．这次课设通过在网上查阅大量资料、程序以及一些学术论文，很好的对内排序算法进行了研究，特别对数据结构这门课所学到的内容付诸于实践，加深了理解。另外，还学到了一写别的方面的知识。这次课设做还有许多没有考虑周到的地方，希望老师指出。6参考文献[1]严蔚敏吴伟民，数据结构（C语言版），北京:清华大学出版社,2007。[2]汪祖柱沈晓潞，基于C语言实现的若干排序算法和分析，安徽电气工程职业学院学报，第九卷第一期。[3]王莉，常用内部排序算法的比较与选择，软件导刊，2006年1月号。[4]赵延惠，排序方法及效率浅析，思茅师范高等专科学校学报，第18卷附录：程序#includeiostream#includestdio.h#includestdlib.h#includetime.h#includeiomanip#defineMAX100000000usingnamespacestd;voidprint(longR[],longn){for(inti=1;i=n;i++)coutsetw(4)R[i];}//------------------------------------------------------------------------------//冒泡排序//------------------------------------------------------------------------------longBubblesort(longR[],longn){longy=1;longi,BT=0;i=n;while(i1){longlastExchangeIndex=1;//表示已经有序for(longj=1;ji;j++)if(R[j+1]R[j]){longt=R[j];R[j]=R[j+1];R[j+1]=t;BT++;lastExchangeIndex=j;//记下进行的位置}i=lastExchangeIndex;//本趟进行过交换的最后一个记录的位置cout第y趟:;y++;for(longx=1;x=i;x++)coutsetw(4)R[x];coutsetw(3)[R[i+1];for(x=i+2;x=n;x++)coutsetw(4)R[x];cout];coutendl;}returnBT;}//------------------------------------------------------------------------------//选择排序//------------------------------------------------------------------------------//staticlongST=0;longSelectMinKey(longR[],longi,longn)//在R[i..R.length]中选择关键字最小的记录{longtemp=i;//记录最小的元素值的位置for(intj=i;j=n;j++){if(R[temp]R[j]){temp=j;//ST++;}}returntemp;}longselectsort(longR[],longn){longj,i,t;longy=1;intST=0;for(i=1;in;i++){j=SelectMinKey(R