课程设计（论文）各种排序算法性能比较
《课程设计（论文）各种排序算法性能比较》由会员分享，可在线阅读，更多相关《课程设计（论文）各种排序算法性能比较（41页珍藏版）》请在装配图网上搜索。
1、各种排序算法性能比较 毕业论文 各种排序算法性能比较 系 电子信息工程系 专业 电子信息工程技术 姓名 班级 电信083（系统） 学号0801133115 指导教师 职称 讲师 设计时间 2010.11.22－2011.1.8 目录 摘要： 3 第一章、引言 4 1.1、排序算法的背景 4 1.2、排序算法研究现状 5 1.3、排序算法的意义 5 1.4、排序算法
2、设计目标 6 第二章、排序算法概要设计 7 2.1、原始数据 7 2.2、输出数据 7 2.3、数据处理 7 2..4、排序算法数据结构设计 8 2 .5排序算法的性能评价 8 2.6、系统的模块划分及模块功能 9 2.6.1、主程序模块 9 2.6.2可排序表单元模块 9 2.7、模块的测试数据 10 第三章、排序基本算法 11 3.1、直接插入排序函数 11 3.1.1基本原理 11 3.1.2排序过程 11 3.1.3直接插入排序算法 11 3.1.4时间复杂度分析 13 3.2、直接选择排序函数 13 3.2.1基本原理 13 3.2.2排序过程
3、14 3.2.3直接选择排序算法 14 3.2.4 时间复杂度分析 15 3.3冒泡排序函数 16 3.3.1基本原理 16 3.3.2排序过程 16 3.3.3冒泡排序算法 18 3.3.4 时间复杂度分析 19 3.4 Shell排序函数 19 3.4.1基本原理 19 3.4.2排序过程 20 3.4.3 Shell排序算法 21 3.4.4时间复杂度分析 22 3.5堆排序函数 23 3.5.1基本原理 23 3.5.2排序过程 23 3.5.3堆排序算法 27 3.6快速排序函数 28 3.6.1基本原理 28 3.6.2排序过程 29 3.6
4、.3快速排序算法 31 3.6.4快速排序时间复杂度分析 33 3.7排序主调用函数 33 3.7.1基本原理 33 3.7.2排序主调用算法 34 3.7.3排序主调用时间复杂度分析 35 第四章、运行与测试 36 第五章、结论 38 致谢 39 参考文献 40 摘要： 在这两年的专业基础课的学习过程中，我们学习了程序设计基础，面向对象程序设计，数据结构——使用C++语言描述等课程。
5、使得我们可以综合运用所学知识，更进一步的理解各个课程之间的联系。不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在这个过程中我遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些知识理解得不够深刻。 我这次的题目是各种排序性能的比较，这就要求我首先必须掌握各种排序的原理，并且还要把各个排序结合起来综合考虑。我在实现排序功能是没有遇到太大的问题，但在进行移动次数，比较次数和交换次数的统计中始终无法得出正确的结果，最终在指导老师的帮助下才完成。在程序写好后，选择用来测试的数据也很重要，否则体现不出一些问题。在这个程序中，如果排序的数据太少，则无法体现时间排名
6、。 通过这次课程设计，使我对数据结构有了更进一步的认识和了解，要通过不断的上机操作才能更好地学习它，我也发现我的许多不足之处，对C++语言的一些库函数不太了解，不能熟练掌握各种常用函数的功能，对函数调用的正确使用不够熟悉，对C++中经常出现的错误也不熟悉。通过这次课程设计，我更加体会到了实践的重要性。 ！ 排序算法是数据结构这门课程核心内容之 · 。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中）听涉及的对象在计算机中对它们进行处理。木文首先介绍排序的一些基木概念和一些常用的排序方法，然后利用
7、VC + ＋开发 · 个数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法（有冒泡排序、选择排序、直接插入排序、希尔排序、快速排序、堆排序等）表示出来。该项目在收集各种排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行程。 所使用的编程环境为TURBOC2。通过实验可知，一般情况下,记录规模较小时，直接插入排序较好；当记录规模较大且无序时，快速排序较好。 关键字：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序； 第一章、引言 1.1、排序算法的背景 21世
8、纪是“信息”主导的世纪，是崇尚“创新与个性”发展的时代，体现“以人为本”、构建“和谐社会”是社会发展的主流。然而随着全球经济一体化进程的不断推进，市场与人才的竞争日趋激烈。对于国家倡导发展的IT产业，需要培养大量的、适应经济和科技发展的计算机人才。 众所周知，近年来，一些用人单位对部分大学毕业生到了工作岗位后，需要1～2年甚至多年的训练才能胜任工作的“半成品”现象反映强烈。从中反映出单位对人才的需求越来越讲究实用，社会要求学校培养学生的标准应该和社会实际需求的标准相统一。对于IT业界来讲，一方面需要一定的科研创新型人才，从事高端的技术研究，占领技术发展的高地；另一方面，更需要计算机工程应用、
9、技术应用及各类服务实施人才，这些人才可统称“应用型”人才。 应用型专科教育，简单地讲就是培养高层次应用型人才的本科教育。其培养目标应是面向社会的高新技术产业，培养在工业、工程领域的生产、建设、管理、服务等第一线岗位，直接从事解决实际问题、维持工作正常运行的高等技术应用型人才。这种人才，一方面掌握某一技术学科的基本知识和基本技能，另一方面又具有较强的解决实际问题的基本能力，他们常常是复合性、综合性人才，受过较为完整的、系统的、有行业应用背景的“职业” 项目训练，其最大的特色就是有较强的专业理论基础支撑，能快速地适应职业岗位并发挥作用。因此，可以说“应用型人才培养既有本科人才培养的一般要求，又有
10、强化岗位能力的内涵，它是在本科基础之上的以‘工程师’层次培养为主的人才培养体系”，人才培养模式必须吸取一般本科教育和职业教育的长处，兼蓄并顾。“计算机科学与技术”专业教学指导委员会已经在研究并指导实施计算机人才的“分类”培养，这需要我们转变传统的教育模式和教学方法，明确人才培养目标，构建课程体系，在保证“基础的前提”下，重视素质的养成，突出“工程性”、“技术应用性”、“适应性”概念，突出知识的应用能力、专业技术应用能力、工程实践能力、组织协调能力、创新能力和创业精神，较好地体现与实施人才培养过程的“传授知识，训练能力，培养素质”三者的有机统一。 排序算法是在整个计算机科学一与技术领域上广泛被
11、使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人一 I ' －智能等的重要基础，广泛的应用于信息学、系统丁；程等各种领域。本人在研究各种算法的过程中，对其特点、效率、适用性等在不同的数据集卜做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行过程，目的有以下五个方面：做算法的对比研究，培养研究能力；开发一个独立的软件，培养程序设计和软件开发能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；为教学服务，研究结果 nJ 对抽象的 《 算法与数据结构 》 的教学有一定的辅助作用。
12、排序是计算机科学中最重要的研究问题之一, 它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。其功能是将一个数据元素的任意序列重新排列成一个按关键字有序的序列。 1.2、排序算法研究现状 随着计一算湘 L 技术的口益发展，其应用旱已不局限于简单的数值运算。而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利川计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。近来国内外专家学者们对
13、排序算法又有了新的研究和发现。例如：我国山东大学的张峰和张金屯两位教授共同研究了 《 我国植被数量分类和排序研究进展 》 这课题。很值得有关部门去学习和研究。 1.3、排序算法的意义 排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。 排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序等六类。 此实验通过对直接插入排序；直接
14、选择排序；起泡排序；Shell排序；快速排序；堆排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力 1.4、排序算法设计目标 本课程设计对以下排序算法进行比较：直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序 待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、表格数据汇总数据，以便对这
15、些内部排序算法进行性能分析。 本课程设计首先介绍排序的一些基本概念和一些常用的排序方法，然后利用 VC 十＋开发一个数据结构的演示系统；该演示系统可以通过操作把数据结构中的主要排序常见的排序算法（直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序）表示出来。该项目在收集齐种排序方法的基础上，对其特点、效率、适用性等在不同的数据集上做全面的分析和比较，并以动态演示的方式展示一些经典排序算法运行程。 第二章、排序算法概要设计 2.1、原始数据 用户输入记录的个数，数据由随机数产生器生成。
16、 2.2、输出数据 产生的随机数分别用直接插入排序；直接选择排序；起泡排序；Shell排序；快速排序；堆排序这些排序方法进行排序，输出关键字的比较次数和移动次数。 2.3、数据处理 主程序 产生1组随机数 起泡 排序 Shell排序 快速 排序 直接选择排序 堆排序 记录关键字的比较次数和移动次数 将随机数保存在数组中 循环20次 输出关键字的比较次数、移动次数的平均值 直接选择排序 2..4、排序算法数据结构设计 本程序中，考虑的内容就是待排序对象，排序的依据是关键字之间的大小比较，故在每个节点的类型定义中，至少得包含关键字key一项。不失
17、一般性，这里就使用关键词这一项，其他都省略，具体应用加上其他数据项即可。被排序对象是由一个个节点够成，一个排序对象呢包含一系列指向一串节点的指针，排序对象的长度。本程序功能简单。 typedef struct { int key; /*关键字*/ }RecordNode; /*排序节点的类型*/ typedef struct { RecordNode *record; int n; /*排序对象的大小*/ }SortObject; /*排序节点的类型*/ 2 .5排序算法的性能评价 ( 1 ）执行时问和所需的辅助空间若排序算法所需的辅助空间并不依赖 J 七问题的规
18、模 I , ，即辅助空问是 o ( l ) ，则称之为就地排序（ In 一 PlaCe Sort ）。非就地排序一般要求的辅助空问为 o (n ）。 ( 2 ）算法本身的复杂程度排序算法的时间开销：大多数排序算法的时问开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。 2.6、系统的模块划分及模块功能 Main Sort Method Quick Sort HeapSort InsertSort Select Sort BubbleSort ShellSort
19、 Quick Output 2.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 lo
20、ng *compare,unsigned long *exchange) D．Shell排序 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
21、,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）
22、时，记录的集合被划分为两个区间[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 （将前两个数据排序） 第二趟
23、： [ 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
24、(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
for(i=0;i
25、
while((temp.key
26、or); } 哨兵（监视哨）有两个作用：一是作为临变量存放R[i]（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。 当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。 3.1.4时间复杂度分析 直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动
27、元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。 3.2、直接选择排序函数 3.2.1基本原理 待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟从 n 个记录中找出关键码最小的记录与第个记录交换；第二趟，从第二个记录开始的， 2 一 1 个记录中再选出关键码最小的记录与第二个记录交换；如此，第 i 趟，则从第 i 个记录开始的 n 一
28、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
29、 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 3.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) {
30、printf("OverFollow!");
getchar();
exit(1);
}
for(i=0;i
31、tor->record[j].key
32、每次进入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换. 3.2.4 时间复杂度分析 该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)。 3.3冒泡排序函数 3.3.1基本原理 在每一趟冒泡排序中，依次比较相邻的两个关键字大小，
33、若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在序列（I[0]~I[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组J[1..n]垂直排列，每个记录J[i]看作是重量为J[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。
34、 3.3.2排序过程 将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 （1）初始 R[1..n]为无序区。 （2）第一趟扫描 从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R
35、[j+1].key 36、3 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- 37、1 Do //做N-1趟排序//
begin
NoSwap := True; //置未排序的标志//
For J := N - 1 DownTo 1 Do //从底部往上扫描//
begin
If R[J+1]< R[J] Then //交换元素//
begin
Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
NoSwap := False
end;
end;
If NoSwap Then Return//本趟排序中未发生交换，则终止算法//
end
38、 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!");
39、 getchar();
exit(1);
}
for(i=0;i 40、d[j+1].key 41、“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 [算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录J[i]看作是重量为J[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组J：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止
3.3.4 时间复杂度分析
当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。当原始数据反向有序时，冒 42、泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟需作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O(n2)。
3.4 Shell排序函数
3.4.1基本原理
Shell排序又称缩小增量排序,Shell排序法是以创建者Donald Shell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d1 43、有距离为d1倍数的记录放在一组中，先在各组内排序；然后去d2 44、
|-------------------|
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
45、 |------------|------------|
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 97
3.4.3 Shell排序算法
void ShellSort(SortOb 46、ject *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;i 47、++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i 48、 while(j>=0&&temp.key 49、ree(pvector);
}
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
3.4.4时间复杂度分析
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱， 50、所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为O(n ^2)。
3.5堆排序函数
3.5.1基本原理
堆排序思想很简单，就是每次把关键词调整为堆，取出堆顶元素与堆中最后一个元素交换，同时令堆得大小减一，把剩余的一些元素重新调整为堆，重复此过程，直到堆中只剩一个元素，n 个关键字序列 kl , k2 ， … ， kn称为堆，当且仅当该序列满足如下性质（简称为堆性质） : ( l ) ki<= k2i 且 ki<=k2i+1或（ 2 ）ki>= k2i 且 ki>=k2i+1。若将此序列所存储的向量 R 「 1…n ］看做是一棵完全二叉树的存储结构，则堆实质上是满足如下 51、性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意： ① 堆中任一子树亦是堆。 ② 以上讨论的堆实际上是人叉堆，类似地可定义 k 叉堆。
3.5.2排序过程
堆排序是一树形选择排序。堆排序的特点是：在排序过程中，将 R 「1… n 〕 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之问的内在关系，在当前无序区中选抒关键字最大（或最小）的记录。下面将从实际数据中演示其排序中的 52、各个操作。原始数组： 22 53 72 1 1 34 44 11 15 28 3 10 65
第一步，从树顶到树叶把数填充进入，建立堆。红色为卜一次交换的两个数日宇列）。
使记录递增有序，进一步排序。第一次交换：
第二次交换：
第三次交换：
第四次交换：
第五次交换：
第六次交换：
第七次交换：
第八次交换：
第九次交换：
全程交换完成，得到最小值为 3 并且输出它。从序列中删除 3 ，重新建立堆。以次循环，直到全部输出完成为止。
3.5.3堆排序算法
void HeapSort(SortObject *p,u 53、nsigned 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;i 54、vector->record[i]=p->record[i];
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;i>0;i--)
{ temp=pvector->record[0];
pvector->record[0]=pvector->record[i];
pvector->record[ 55、i]=temp;
(*exchange)+=3;
SiftHeap(pvector,i,0,compare,exchange);
}/*重建新堆*/
free(pvector);
}
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
3.5.4时间复杂度分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的 56、比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlog n)。
3.6快速排序函数
3.6.1基本原理
首先我们选择一个中间值 middle （程序中我们可使用数组中间值），把比中问值小的放在其左边，比中问值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架。在待排序的个记录中任意取一个记录（通常取第一个记录）为区分标准，把所有小于该排序的记录移到左边，把所有大于该排序码的记录移到右边，中级放所选记录，为一趟快速排序。然后对前后两个子序列分别重新上述过程，直到所有记录都排好序。对任意给定的序列中某个元素，经过一趟排序后，将原 57、序列分割成两个子序列(Rp(0),Rp(1),…,Rp(s-1))和(Rp(s+1),Rp(s+2),…,Rp(n-1))，其中前一个子序列中的所有元素的关键词均小于或等于该元素的关键词值Kp(s)，后一个子序列中元素的关键词均大于或等于Kp(s)。称该元素Rp(s)为分割元素，子序列(Rp(0),Rp(1),…,Rp(s-1))为其低端序列，(Rp(0),Rp(1),…,Rp(s-1))为其高端序列。很明显，以后只需对低端和高端序列分别进行快速排序，直到子序列为空或只有一个元素时结束，最后得到有序序列。总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的 58、子表长度为1！
3.6.2排序过程
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
59、 5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
60、 ( 按照算法的第三步从后面开始找
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 61、 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后 62、把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 { 63、97}
49 {65} 结束
结束
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；
3）、利用分 64、治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下，那么第一躺快速排序的过程是：
数组下标： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
（1） 36 36 18 53 72 30 48 93 65、 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 4 66、8 93 72 53
通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序
3.6.3快速排序算法
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)/*6.快速排序*/
{ int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{ while((pvector->record[j].key>=temp.key)&&(j>i))
{ (*compare)++;
j--;
}
if(i
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
