课程设计（论文）-各种排序算法性能比较.doc

各种排序算法性能比较毕业论文 各种排序算法性能比较 系 电子信息工程系 专业 电子信息工程技术 姓名 班级 电信083（系统） 学号0801133115指导教师 职称 讲师 设计时间 2010.11.222011.1.8 目录摘要：3第一章、引言41.1、排序算法的背景41.2、排序算法研究现状51.3、排序算法的意义51.4、排序算法设计目标6第二章、排序算法概要设计72.1、原始数据72.2、输出数据72.3、数据处理72.4、排序算法数据结构设计82 .5排序算法的性能评价82.6、系统的模块划分及模块功能92.6.1、主程序模块92.6.2可排序表单元模块92.7、模块的测试数据10第三章、排序基本算法113.1、直接插入排序函数113.1.1基本原理113.1.2排序过程113.1.3直接插入排序算法113.1.4时间复杂度分析133.2、直接选择排序函数133.2.1基本原理133.2.2排序过程143.2.3直接选择排序算法143.2.4 时间复杂度分析153.3冒泡排序函数163.3.1基本原理163.3.2排序过程163.3.3冒泡排序算法183.3.4 时间复杂度分析193.4 shell排序函数193.4.1基本原理193.4.2排序过程203.4.3 shell排序算法213.4.4时间复杂度分析223.5堆排序函数233.5.1基本原理233.5.2排序过程233.5.3堆排序算法273.6快速排序函数283.6.1基本原理283.6.2排序过程293.6.3快速排序算法313.6.4快速排序时间复杂度分析333.7排序主调用函数333.7.1基本原理333.7.2排序主调用算法343.7.3排序主调用时间复杂度分析35第四章、运行与测试36第五章、结论38致谢39参考文献40 摘要：在这两年的专业基础课的学习过程中，我们学习了程序设计基础，面向对象程序设计，数据结构使用c+语言描述等课程。使得我们可以综合运用所学知识，更进一步的理解各个课程之间的联系。不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在这个过程中我遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些知识理解得不够深刻。我这次的题目是各种排序性能的比较，这就要求我首先必须掌握各种排序的原理，并且还要把各个排序结合起来综合考虑。我在实现排序功能是没有遇到太大的问题，但在进行移动次数，比较次数和交换次数的统计中始终无法得出正确的结果，最终在指导老师的帮助下才完成。在程序写好后，选择用来测试的数据也很重要，否则体现不出一些问题。在这个程序中，如果排序的数据太少，则无法体现时间排名。通过这次课程设计，使我对数据结构有了更进一步的认识和了解，要通过不断的上机操作才能更好地学习它，我也发现我的许多不足之处，对c+语言的一些库函数不太了解，不能熟练掌握各种常用函数的功能，对函数调用的正确使用不够熟悉，对c+中经常出现的错误也不熟悉。通过这次课程设计，我更加体会到了实践的重要性。！排序算法是数据结构这门课程核心内容之 。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中）听涉及的对象在计算机中对它们进行处理。木文首先介绍排序的一些基木概念和一些常用的排序方法，然后利用 vc + 开发 个数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法（有冒泡排序、选择排序、直接插入排序、希尔排序、快速排序、堆排序等）表示出来。该项目在收集各种排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行程。所使用的编程环境为turboc2。通过实验可知，一般情况下,记录规模较小时，直接插入排序较好；当记录规模较大且无序时，快速排序较好。关键字：直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序；第一章、引言1.1、排序算法的背景21世纪是“信息”主导的世纪，是崇尚“创新与个性”发展的时代，体现“以人为本”、构建“和谐社会”是社会发展的主流。然而随着全球经济一体化进程的不断推进，市场与人才的竞争日趋激烈。对于国家倡导发展的it产业，需要培养大量的、适应经济和科技发展的计算机人才。众所周知，近年来，一些用人单位对部分大学毕业生到了工作岗位后，需要12年甚至多年的训练才能胜任工作的“半成品”现象反映强烈。从中反映出单位对人才的需求越来越讲究实用，社会要求学校培养学生的标准应该和社会实际需求的标准相统一。对于it业界来讲，一方面需要一定的科研创新型人才，从事高端的技术研究，占领技术发展的高地；另一方面，更需要计算机工程应用、技术应用及各类服务实施人才，这些人才可统称“应用型”人才。应用型专科教育，简单地讲就是培养高层次应用型人才的本科教育。其培养目标应是面向社会的高新技术产业，培养在工业、工程领域的生产、建设、管理、服务等第一线岗位，直接从事解决实际问题、维持工作正常运行的高等技术应用型人才。这种人才，一方面掌握某一技术学科的基本知识和基本技能，另一方面又具有较强的解决实际问题的基本能力，他们常常是复合性、综合性人才，受过较为完整的、系统的、有行业应用背景的“职业” 项目训练，其最大的特色就是有较强的专业理论基础支撑，能快速地适应职业岗位并发挥作用。因此，可以说“应用型人才培养既有本科人才培养的一般要求，又有强化岗位能力的内涵，它是在本科基础之上的以工程师层次培养为主的人才培养体系”，人才培养模式必须吸取一般本科教育和职业教育的长处，兼蓄并顾。“计算机科学与技术”专业教学指导委员会已经在研究并指导实施计算机人才的“分类”培养，这需要我们转变传统的教育模式和教学方法，明确人才培养目标，构建课程体系，在保证“基础的前提”下，重视素质的养成，突出“工程性”、“技术应用性”、“适应性”概念，突出知识的应用能力、专业技术应用能力、工程实践能力、组织协调能力、创新能力和创业精神，较好地体现与实施人才培养过程的“传授知识，训练能力，培养素质”三者的有机统一。排序算法是在整个计算机科学一与技术领域上广泛被使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人一 i 智能等的重要基础，广泛的应用于信息学、系统丁；程等各种领域。本人在研究各种算法的过程中，对其特点、效率、适用性等在不同的数据集卜做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行过程，目的有以下五个方面：做算法的对比研究，培养研究能力；开发一个独立的软件，培养程序设计和软件开发能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；为教学服务，研究结果 nj 对抽象的 算法与数据结构 的教学有一定的辅助作用。排序是计算机科学中最重要的研究问题之一, 它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。1.2、排序算法研究现状随着计一算湘 l 技术的口益发展，其应用旱已不局限于简单的数值运算。而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利川计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。近来国内外专家学者们对排序算法又有了新的研究和发现。例如：我国山东大学的张峰和张金屯两位教授共同研究了 我国植被数量分类和排序研究进展 这课题。很值得有关部门去学习和研究。1.3、排序算法的意义排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序等六类。此实验通过对直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力1.4、排序算法设计目标本课程设计对以下排序算法进行比较：直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、表格数据汇总数据，以便对这些内部排序算法进行性能分析。本课程设计首先介绍排序的一些基本概念和一些常用的排序方法，然后利用 vc 十开发一个数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法（直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序）表示出来。该项目在收集齐种排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行程。第二章、排序算法概要设计2.1、原始数据用户输入记录的个数，数据由随机数产生器生成。2.2、输出数据产生的随机数分别用直接插入排序；直接选择排序；起泡排序；shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3、数据处理主程序产生1组随机数起泡排序shell排序快速排序直接选择排序堆排序记录关键字的比较次数和移动次数将随机数保存在数组中循环20次输出关键字的比较次数、移动次数的平均值直接选择排序 2.4、排序算法数据结构设计本程序中，考虑的内容就是待排序对象，排序的依据是关键字之间的大小比较，故在每个节点的类型定义中，至少得包含关键字key一项。不失一般性，这里就使用关键词这一项，其他都省略，具体应用加上其他数据项即可。被排序对象是由一个个节点够成，一个排序对象呢包含一系列指向一串节点的指针，排序对象的长度。本程序功能简单。typedef structint key; /*关键字*/recordnode; /*排序节点的类型*/typedef structrecordnode *record;int n; /*排序对象的大小*/sortobject; /*排序节点的类型*/2 .5排序算法的性能评价 ( 1 ）执行时问和所需的辅助空间若排序算法所需的辅助空间并不依赖 j 七问题的规模 i , ，即辅助空问是 o ( l ) ，则称之为就地排序（ in 一 place sort ）。非就地排序一般要求的辅助空问为 o (n ）。 ( 2 ）算法本身的复杂程度排序算法的时间开销：大多数排序算法的时问开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。2.6、系统的模块划分及模块功能mainsortmethodquicksortheapsortinsertsortselectsortbubblesortshellsortquickoutput2.6.1、主程序模块void main（）2.6.2可排序表单元模块a直接插入排序void insertsort (sortobject *p,unsigned long *compare,unsigned long *exchange)b.直接选择排序void selectsort(sortobject *p,unsigned long *compare,unsigned long *exchange) c.冒泡排序void bubblesort (sortobject *p,unsigned long *compare,unsigned long *exchange)dshell排序void shellsort(sortobject *p,int d,unsigned long *compare,unsigned long *exchange)e堆排序 void siftheap(sortobject *pvector,int size,int p,unsigned long *compare,unsigned long *exchange)/*调整为堆*/f快速排序void quicksort(sortobject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/g排序主调用函数void sortmethod(void)2.7、模块的测试数据以关键字的数目分别为20，100，500为例,作为测试数据第三章、排序基本算法3.1、直接插入排序函数3.1.1基本原理假设待排序的n个记录r0,r1,rn顺序存放在数组中，直接插入法在插入记录ri（i=1,2,n-1）时，记录的集合被划分为两个区间r0,ri-1和ri+1,rn-1,其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码ki与ki-1ki-2，k0依次比较，找出应该插入的位置，将记录ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。3.1.2排序过程关键字： 10 3 25 20 8 第一趟： 3 10 25 20 8 （将前两个数据排序）第二趟： 3 10 25 20 8 （将 25 放入前面数据中的适当位置）第三趟： 3 10 20 25 8 （将 20 放入适当的位置）第四趟： 3 8 10 20 25 （将 8 放入适当的位置）3.1.3直接插入排序算法void insertsort(sortobject *p,unsigned long *compare,unsigned long *exchange)int i,j;recordnode temp; sortobject *pvector;if(pvector=(sortobject *)malloc(sizeof(sortobject)=null)printf(overfollow!);getchar();exit(1);for(i=0;in;i+)/* 复制数组*/pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=1;in;i+) temp=pvector-recordi; (*exchange)+; j=i-1; while(temp.keyrecordj.key)&(j=0) (*compare)+; (*exchange)+; pvector-recordj+1=pvector-recordj; j-; if(j!=(i-1) pvector-recordj+1=temp; (*exchange)+; free(pvector);哨兵（监视哨）有两个作用：一是作为临变量存放ri（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为o(n)，最坏情况是文件初态为反序，相应的时间复杂度为o(n2)，算法的平均时间复杂度是o(n2)。算法的辅助空间复杂度是o(1)，是一个就地排序。3.1.4时间复杂度分析直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是o(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为o(n2)。 3.2、直接选择排序函数3.2.1基本原理待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟从 n 个记录中找出关键码最小的记录与第个记录交换；第二趟，从第二个记录开始的， 2 一 1 个记录中再选出关键码最小的记录与第二个记录交换；如此，第 i 趟，则从第 i 个记录开始的 n 一 i + l 个记录中选出关键码最小的记录一与第 i 个记录交换，占到招个序列按关键码有序。3.2.2排序过程【示例】：初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 973.2.3直接选择排序算法void selectsort(sortobject *p,unsigned long *compare,unsigned long *exchange) int i,j,k; recordnode temp;sortobject *pvector;if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!);getchar();exit(1); for(i=0;in;i+)/*复制数组*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) (*compare)+; if(pvector-recordj.keyrecordk.key) k=j; if(k!=i) temp=pvector-recordi; pvector-recordi=pvector-recordk; pvector-recordk=temp; ( *exchange)+=3; free(pvector);选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.3.2.4 时间复杂度分析该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为o(n2)。3.3冒泡排序函数3.3.1基本原理在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列（i0in-1）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到in-1中，下一趟只需在子序列（i0in-2）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组j1.n垂直排列，每个记录ji看作是重量为ji.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组r：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。3.3.2排序过程将被排序的记录数组r1.n垂直排列，每个记录ri看作是重量为ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组r：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。（1）初始 r1.n为无序区。（2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(rn，rn-1)，(rn-1，rn-2)，(r2，r1)；对于每对气泡(rj+1，rj)，若rj+1.keyrj.key，则交换rj+1和rj的内容。 第一趟扫描完毕时，最轻的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置r1上。（3）第二趟扫描 扫描r2.n。扫描完毕时，次轻的气泡飘浮到r2的位置上 最后，经过n-1趟扫描可得到有序区r1.n 第i趟扫描时，r1.i-1和ri.n分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置ri上，结果是r1.i变为新的有序区。49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 procedure bubblesort(var r : filetype) /从下往上扫描的起泡排序/ begin for i := 1 to n-1 do /做n-1趟排序/ begin noswap := true; /置未排序的标志/ for j := n - 1 downto 1 do /从底部往上扫描/ begin if rj+1 rj then /交换元素/ begin temp := rj+1; rj+1 := rj; rj := temp; noswap := false end; end; if noswap then return/本趟排序中未发生交换，则终止算法/ end end; /bubblesort/3.3.3冒泡排序算法void bubblesort(sortobject *p,unsigned long *compare,unsigned long *exchange) int i,j,noswap; recordnode temp; sortobject *pvector; if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(i=0;in-1;i+) noswap=1; for(j=0;jn-i-1;j+) (*compare)+; if(pvector-recordj+1.keyrecordj.key) temp=pvector-recordj; pvector-recordj=pvector-recordj+1; pvector-recordj+1=temp; (*exchange)+=3; noswap=0; if(noswap) break; free(pvector);起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 算法思想：将被排序的记录数组r1.n垂直排列，每个记录ji看作是重量为ji.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组j：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止3.3.4 时间复杂度分析当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是o(n)。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟需作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为o(n2)。3.4 shell排序函数3.4.1基本原理shell排序又称缩小增量排序,shell排序法是以创建者donald shell的名字命名的.shell排序法是对相邻指定距离(称为间隔)的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,shell排序也就完成了其处理过程.先取一个整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2d1重复上诉分组和排序工作；直至所取的增量dt=1(dtdt-ld2d1)，即所有记录放在同一组中进行直接插入，直到di=1，即所有记录放在一组中为止3.4.2排序过程先取一个正整数d1n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止 初始：d5 49 38 65 97 76 13 27 49* 55 04 49 13 |-| 38 27 |-| 65 49* |-| 97 55 |-| 76 04 |-| 一趟结果 13 27 49* 55 04 49 38 65 97 76 d=3 13 27 49* 55 04 49 38 65 97 76 13 55 38 76 |-|-|-| 27 04 65 |-|-| 49* 49 97 |-|-| 二趟结果 13 04 49* 38 27 49 55 65 97 76 d=1 13 04 49* 38 27 49 55 65 97 76 |-|-|-|-|-|-|-|-|-| 三趟结果 04 13 27 38 49* 49 55 65 76 973.4.3 shell排序算法void shellsort(sortobject *p,int d,unsigned long *compare,unsigned long *exchange) int i,j,increment; recordnode temp; sortobject *pvector; if(pvector=(sortobject*)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi; pvector-n=p-n; *compare=0; *exchange=0; for(increment=d;increment0;increment/=2) for(i=increment;in;i+) temp=pvector-recordi; (*exchange)+; j=i-increment; while(j=0&temp.keyrecordj.key) (*compare)+; pvector-recordj+increment=pvector-recordj; (*exchange)+;j-=increment; pvector-recordj+increment=temp; (*exchange)+; free(pvector);当增量d=1时，shellpass和insertsort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。3.4.4时间复杂度分析希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为o(n 2)。3.5堆排序函数3.5.1基本原理堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程，直到堆中只剩一个元素，n 个关键字序列 kl , k2 ， ， kn称为堆，当且仅当该序列满足如下性质（简称为堆性质） : ( l ) ki= k2i 且 ki= k2i 且 ki=k2i+1。若将此序列所存储的向量 r 1n 看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。注意： 堆中任一子树亦是堆。 以上讨论的堆实际上是人叉堆，类似地可定义 k 叉堆。3.5.2排序过程堆排序是一树形选择排序。堆排序的特点是：在排序过程中，将 r 1 n 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之问的内在关系，在当前无序区中选抒关键字最大（或最小）的记录。下面将从实际数据中演示其排序中的各个操作。原始数组： 22 53 72 1 1 34 44 11 15 28 3 10 65 第一步，从树顶到树叶把数填充进入，建立堆。红色为卜一次交换的两个数日宇列）。使记录递增有序，进一步排序。第一次交换：第二次交换：第三次交换：第四次交换：第五次交换：第六次交换：第七次交换：第八次交换：第九次交换：全程交换完成，得到最小值为 3 并且输出它。从序列中删除 3 ，重新建立堆。以次循环，直到全部输出完成为止。3.5.3堆排序算法void heapsort(sortobject *p,unsigned long *compare,unsigned long *exchange)/*5.堆排序*/ int i,n; recordnode temp; sortobject *pvector; if(pvector=(sortobject *)malloc(sizeof(sortobject)=null) printf(overfollow!); getchar(); exit(1); for(i=0;in;i+)/* 复制数组*/ pvector-recordi=p-recordi;pvector-n=p-n;*compare=0;*exchange=0;n=pvector-n;for(i=n/2-1;i=0;i-)siftheap(pvector,n,i,compare,exchange);/*首先构造第一个堆*/for(i=n-1;i0;i-) temp=pvector-record0; pvector-record0=pvector-recordi; pvector-recordi=temp; (*exchange)+=3; siftheap(pvector,i,0,compare,exchange);/*重建新堆*/free(pvector);当增量d=1时，shellpass和insertsort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件j0，以防下标越界。3.5.4时间复杂度分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用heapify实现的。堆排序的最坏时间复杂度为o(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度o(nlog n)。3.6快速排序函数3.6.1基本原理首先我们选择一个中间值 middle （程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该排序码的记录