排序算法比较

南京审计学院信息科学学院计算机科学与技术系数据结构课程设计报告课程设计题目：用程序实现多种程序算法姓名：吴彤学号：09070517指导教师：陈一飞完成时间：2011.12.2数据结构课程设计成绩评定序号评定项目分值得分1选题合理、目的明确102设计方案正确，具有可行性、创新性203程序运行结果正确204态度认真、学习刻苦、遵守纪律155设计报告的规范化、参考文献充分（不少于5篇）106答辩：思路清晰，语言表达准确，概念清楚、正确25最后得分指导老师（签名）日期年月日目录(参考)1系统分析....................................................................................................................11.1课程设计内容..................................................................................................21.2系统功能需求分析..........................................................................................31.3数据结构设计..................................................................................................42系统设计....................................................................................................................52.1总体设计..........................................................................................................52.2各功能模块的设计..........................................................................................62.2.1..................................................................................................................62.2.2..................................................................................................................72.2.3..................................................................................................................82.2.4..................................................................................................................92.2.5................................................................................................................102.2.6................................................................................................................112.2.7................................................................................................................122.2.8................................................................................................................132.2.9................................................................................................................143系统调试..................................................................................................................154总结..........................................................................................................................205参考文献..................................................................................................................22附录（源代码）1.1课程设计内容每位同学必须完成(1)直接插入排序(2)折半插入排序(3)冒泡排序(4)简单选择排序(5)快速排序(6)堆排序(7)归并排序以上这些算法，并完成这些算法的性能分析（从时间复杂度和空间复杂度两个方面进行比较分析）报告。1.2各排序算法性能分析1.插入排序、冒泡排序是稳定的，而选择排序、快速排序、堆排序是不稳定的2.1冒泡排序：冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。算法时间复杂度是O(n^2)。2.2选择排序选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。算法复杂度是O(n^2)。2.3插入排序插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j]≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。直接插入排序是稳定的。算法时间复杂度是O(n^2)2.4堆排序堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。算法时间复杂度O(nlogn)。2.5归并排序设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。时间复杂度是O(nlog2n)。2.6快速排序快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。算法时间复杂度O(nlog2n)总结：冒泡排序、插入排序以及快速排序对数据的有序性比较敏感，尤其是冒泡排序和插入排序；相比而言，选择排序不关心表的初始次序，它的最坏情况的排序时间与其最佳情况没多少区别，其比较次数为)1(21nn，但选择排序可以非常有效的移动元素。因此对次序近乎正确的表，选择排序可能比插入排序慢很多。冒泡排序在最优情况下只需要经过n-1次比较即可得出结果（即对于完全正序的表），最坏情况下也要进行)1(21nn次比较，与选择排序的比较次数相同，但数据交换的次数要多余选择排序，因为选择排序的数据交换次数顶多为1n，而冒泡排序最坏情况下的数据交换)1(21nn。冒泡排序不一定要进行1n趟，但由于它的记录移动次数较多，所以它的平均时间性能比插入排序要差一些。插入排序在最好的情况下有最少的比较次数1n，但是它在元素移动方面效率非常低下，因为它只与毗邻的元素进行比较，效率比较低。快速算法的平均时间复杂度为)lg(0nn，平均而言，快速排序是基于关键字比较的内部排序算法中速度最快者；但是由于快速排序采用的是递归的方法，因此当序列的长度比较大时，对系统栈占用会比较多。快速算法尤其适用于随机序列的排序。因此，平均而言，对于一般的随机序列顺序表而言，上述几种排序算法性能从低到高的顺序大致为：冒泡排序、插入排序、选择排序，快速排序。但这个优劣顺序不是绝对的，在不同的情况下，甚至可能出现完全的性能逆转。对于序列初始状态基本有正序，可选择对有序性较敏感的如插入排序、冒泡排序、选择排序等方法。即如下表所示：排序类别时间复杂度空间复杂度插入排序O(n2)1冒泡排序O(n2)1选择排序O(n2)1快速排序O(Nlogn)O(logn)堆排序O(Nlogn)1归并排序O(Nlogn)O(n)附录程序源代码：//直接插入排序#includestdio.h#includestdlib.h#includetime.h#defineN20000clock_tbegin,end;doublecost;voidInsertSort(intr[]){begin=clock();for(inti=2;iN;i++){r[0]=r[i];for(intj=i-1;r[0]r[j];j--)r[j+1]=r[j];r[j+1]=r[0];}end=clock();cost=(double)(end-begin)/CLOCKS_PER_SEC;printf(%lfseconds\n,cost);FILE*fp;fp=fopen(直接选择排序.txt,w);for(i=0;iN;i++)fprintf(fp,%d,r[i]);fprintf(fp,\n\n\n用直接插入算法所用时间为：%f,cost);fclose(fp);}voidmain(){inta[N];srand(time(0));for(inti=0;iN;i++)a[i]=rand()%N;printf(\n\n用直接插入