排序算法的比较

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业排序算法的比较1课程设计名称 排序算法的比较 概述排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。内部排序算法主要分为5 大类，有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括：插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。2使用工具软件 Microsoft Visual C+ 6.03 课程设计内容简介3.1课程设

2、计内容掌握各种排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）的思路核比较他们之间的优劣。3.2 基本要求1.任意性：系统首先生成1000个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间2.友好性：界面要友好，输入有提示，尽量展示人性化3.可读性：源程序代码清晰、有层次 4.健壮性：用户输入非法数据时，系统要及时给出警告信息3.3 课程设计思想 程序设计的总体思路：首先构建main()函数，根据题目的要求，再分别构建四个排序函数：冒泡排序函数（long Bubblesort(long R, long n)）、选择排序函数（long selects

3、ort(long R,long n)）、直接插入排序函数（long insertsort(long R, long n)）和快速排序函数（void QuickSort(long R,long n)）。为了使程序具有可读性和层次感，建立一个导航函数（void DaoHang()）和操作函数（void operate(long a, long n)），其中，void DaoHang()用来告知用户程序的操作流程，void operate(long a, long n)用来接收用户不同的选择，从而调用其它函数。3.4 程序分析3.4.1 存储结构 顺序存储结构（如图1）示意图a0a1a2a3a4图1

4、3.4.2 关键算法分析关键算法1实现四种算法的基本排序功能1冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。实现过程（如图2）。对于数组（21 25 49 16 08）。初态：2125491608第一趟：2125160849第二趟：2116082549第三趟：1608212549第四趟：0816212549图22选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。实现过程（如图3）。

5、对于数组（21 25 49 16 08）。初态：2125491608第一趟：0825491621第二趟：0816492521第三趟：0816212549图33直接插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。实现过程（如图4）。对于数组（21 25 49 16 08）。初态：2125491608第一趟：2125491608第二趟：2125491608第三趟：2125491608第四趟：1621254908第五趟：0816212549图44快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至

6、整个序列排序完成。实现过程（如图5）对于数组（21 25 49 16 08）。初态：R0=212125491608highlow第一趟：R0=210825491608highlowR0=210825491625highlowR0=210816491625highlowR0=210816491625lowhigh R0=210816494925highlowR0=21low=high0816214925图5关键算法二获取当前系统时间，精确到毫秒，分别在代码运行前后调用记录前后时间，再相减即可得到代码运行时间。/以冒泡排序为例start=(double)clock();/开始 Bubblesort

7、(R, n);end=(double)clock();/结束Time = (double)(end-start)/CLK_TCK;/相减，精确到毫秒关键算法三：实现手动与计算机随机双重输入。手动输入检查程序的正确性，计算机随即输入，可以比较各排序算法的性能。void Rand()/随机数函数void HandInput()/手动输入函数关键算法四 纠错功能。在用户输入非法数据时，给予警告，并要求用户重新输入，不必重启程序。3.4.3时间复杂度与空间复杂度：理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示（图6）：排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(

8、n)O(n2)O(1)起泡排序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)图63.4.4 选择排序算法的依据影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下4 点：待排序的记录数目n 的大小。记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小。关键字的结构及其分布情况。对排序稳定性的要求。3.5 程序流程图m

9、ain()输入0输入a输入排序方法输入错误输入错误判断手动还是随机输入(1,2)?HandInput()(手动输入)1Rand();(随机输入)2void DaoHang()void operate()cinai ;/数据存储选择排序方法Void print()结束图73.6 运行环境Microsoft Visual C+ 6.0/WIN32 Console Application3.7运行结果3.7.1当手动输入五个数据时，运行结果（如图8）图83.7.2当选择随机数时，运行结果(如图9)图93.8 得意之处得意之处1将时间精确到毫秒，使得实验结果更容易观察比较。代码如下（冒泡排序为例）：s

10、tart=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-start)/;其中CLK_TCK值为1000，即将时间精确到毫秒（图10）。图10得意之处2将排序过程的每一趟输出，并且将已排好序的用中括号括起来，这样以来，可以直接看出排序过程是否正确以及深入了解排序过程的每一步。如：对于冒泡排序（图11）图11得意之处3冒泡排序算法中，运用做标记的方法，使得排序得到正确结果后，便停止做不必要的循环。代码如下while(i1)long lastExchangeIndex=1;/表示已经

11、有序for(long j=1;ji;j+)if(Rj+1Rj)long t=Rj;Rj=Rj+1;Rj+1=t; BT+;lastExchangeIndex=j;/记下进行的位置i=lastExchangeIndex;/本趟进行过交换的最后一个记录的位置4 课程设计中目前存在问题1交换次数统计不够精确。2无论时间还是移动次数，应该有一个对比结果，不能只是罗列出来。3对于快速排序，存在两个问题。其一，不能两边同时进行排序，使得排序趟数增加；其二，没能格式化输出，使得输出不清晰，不美观。5 自我感受1在初期构思代码的时候，首先构造了各种算法的基本实现代码，已经能够实现四种排序的基本功能，并且测试无

12、误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生函数，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达四种排序算法的简单调用和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。调用精确的系统函数实现时间的统计。此外还添加了一系列优化，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。2程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。因而以后要多花力气学习C+编程语言，必须要加强这方面的训练，这样才能在将

13、编程思想和数据结构转换为代码的时候能得心应手。3这次课设通过在网上查阅大量资料、程序以及一些学术论文，很好的对内排序算法进行了研究，特别对数据结构这门课所学到的内容付诸于实践，加深了理解。另外，还学到了一写别的方面的知识。这次课设做还有许多没有考虑周到的地方，希望老师指出。6参考文献1 严蔚敏 吴伟民，数据结构（C语言版），北京:清华大学出版社,2007。2 汪祖柱 沈晓潞，基于C语言实现的若干排序算法和分析，安徽电气工程职业学院学报，第九卷第一期。3 王莉，常用内部排序算法的比较与选择，软件导刊，2006年1月号。4 赵延惠，排序方法及效率浅析，思茅师范高等专科学校学报，第18卷附录：程序#

14、include #include#include #include #include #define MAX using namespace std;void print(long R,long n)for(int i=1;i=n;i+)coutsetw(4)1)long lastExchangeIndex=1;/表示已经有序for(long j=1;ji;j+)if(Rj+1Rj)long t=Rj;Rj=Rj+1;Rj+1=t; BT+;lastExchangeIndex=j;/记下进行的位置i=lastExchangeIndex;/本趟进行过交换的最后一个记录的位置cout第y趟:;y+

15、;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;coutendl;return BT;/-/选择排序/-/static long ST=0;long SelectMinKey(long R,long i,long n)/在 Ri.R.length 中选择关键字最小的记录long temp=i;/记录最小的元素值的位置for(int j=i;jRj)temp=j;/ST+;return temp;long selectsort(long R,long n)long j,i

16、,t;long y=1;int ST=0;for( i=1;in;i+)j = SelectMinKey(R,i,n);/ 在 L.ri.L.length 中选择关键字最小的记录if (i!=j) / 与第 i 个记录交换t=Ri;Ri=Rj;Rj=t;ST+; cout第y趟: ;y+;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;/print(R,n);coutendl;return ST;/-/直接插入排序/-long insertsort(long R, lon

17、g n)long y=1;long IT=0,j;for(long i=2;i=n;+i)if(RiRi-1)R0=Ri;/复制为哨兵IT=IT+1;for( j=i-1;R0Rj;-j)Rj+1=Rj;/记录后移IT=IT+1;Rj+1=R0;/插入到正确位置IT=IT+1;cout第y趟: ;y+;coutsetw(4)R1;for(long x=2;x=i;x+)coutsetw(4)Rx;cout;for(x=i+1;x=n;x+)coutsetw(4)Rx;coutendl;return IT;/-/快速排序/-static long QT=0;int Partition (long

18、 R, long low, long high,long n)R0 =Rlow; long pivotkey = Rlow; / 枢轴 QT=QT+2;while (lowhigh) while(low=pivotkey)/ 从右向左搜索- high; Rlow = Rhigh;QT=QT+1;while (lowhigh & Rlow=pivotkey)/ 从左向右搜索+ low; Rhigh = Rlow;QT=QT+1;Rlow =R0; QT=QT+1;return low;/ Partitionvoid quicksort (long R, int low, int high,lon

19、g n,long y)/ 对记录序列L.rlow.high进行快速排序if (low high) / 长度大于1 long pivotloc = Partition(R,low,high,n);/ 对 L.rlow.high 进行一次划分QT=QT+1;cout第y趟:;y+;print(R,pivotloc-1);coutsetw(2)Rpivotloc;cout;for(long x=pivotloc+1;x=n;x+)coutsetw(5)Rx;coutendl;quicksort(R, low, pivotloc-1,n,y); / 对低子序列递归排序quicksort(R, pivo

20、tloc+1, high,n,y); / 对高子序列递归排序 / QSortvoid QuickSort(long R,long n) long y=1;quicksort(R,1,n,n,y);/-/操作选择函数/-void operate(long a, long n)void main();long * R = new long n;time_t start, end;/定义两个变量double Time;/排序时间long degree;/排序次数char ch;cout ch;switch(ch)case 1:coutn;coutt=您选择的是冒泡排序=n;for(int i = 1

21、; i =n; i +)/将随机数付给RiRi = ai;start=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);cout n;cout 冒泡排序所用时间：t Time n;cout 冒泡排序交换次数：t degree n;coutn;operate(a, n);break;case 2:coutn;coutt=您选择的是选择排序=n;for(int i = 1; i = n; i +)Ri = ai;start=(dou

22、ble)clock();degree = selectsort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 选择排序所用时间：t Time n;cout 选择排序交换次数：t degree n;cout n;operate(a, n);break;case 3:coutn;coutt=您选择的是直接插入排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();degree = insertsort(R, n);end

23、=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 直接插入排序所用时间： Time n;cout 直接插入排序交换次数： degree n;cout n;operate(a, n);break;case 4:coutn;coutt=您选择的是快速排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();QuickSort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;coutn;cout 快速排序所用时间：t Time n;cout 快速排序交换次数：t QT n;cout n;operate(a, n);break;case a:main();break;de