VC实现排序算法动态演示系统

PAGEPAGE19摘要排序是计算机科学的一个重要领域，并广泛应用于计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域。本文选择其中最基本也是最常用的一些算法进行讨论，介绍它们的基本思想和实现过程，分析各种排序算法的性能，并且采用VS2008作为开发工具以windowsSDK为编程环境动态地演示算法的排序过程。排序方法大致可分为插入排序、交换排序、选择排序、归并排序四大类，他们的性能分析参数则以时间复杂度、空间复杂度和稳定性为主。其中属于交换排序的快速排序方法在平均时间上最省，但在最坏情况下不如堆排序和归并排序，堆排序和归并排序在所需时间和所需空间上成互补情况；几种时间复杂度为O(n2)的简单排序则是在稳定性上占有优势而且实现方法简单，在序列基本有序和需排序对象比较少的情况下，直接插入排序是最佳排序；总体上来讲，没有哪一种排序方法是绝对优势的，在不同情况下需要选择合适的排序方法，如果需要还可以混合使用已达到效果最佳。排序算法的演示系统由C语言调用windowsAPI完成图形编程，采用数据线的虚实线变换和操作线的移动交互演示，以定时器为基数刷新图像达到动态演示的效果。软件还可以输出排序过程中的数据和排序后的数据，以及显示当前排序方法的性能参数等，最大化地做到人性化人机交互。软件在教学或者排序方法学习方面都有很好的用途。【关键词】插入排序交换排序选择排序归并排序时间复杂度空间复杂度windowsSDKABSTRACTSortingisanimportantareaofcomputerscience,andiswidelyusedincomputergraphics,computerassistdesign,robotics,patternrecognitionandstatisticsandotherfields.Thischoiceofwhichsomeofthemostbasicandmostcommonlyusedalgorithmsdiscussed,introducingtheirbasicideasandimplementationprocess,toanalyzetheperformanceofsortingalgorithms,andusingVS2008windowsSDKasadevelopmenttoolfortheprogrammingenvironmenttodynamicallydemonstratprocessofsortingalgorithms.

Sortingmethodcanbedividedintoinsertionsort,exchangesort,selectionsort,mergesortfourcategories,andtheirperformanceanalysisparametersZeyitimecomplexity,spacecomplexityandstabilityoriented.Whichissortofthequicksortmethodforexchangingtheaveragetimemostprovinces,butnotasgoodasintheworstcaseheapsortandmergesort,heapsortandmergesortintimeandspacerequiredascomplementarysituation;severaltimecomplexitydegreeisO(n2)sortingisasimpleadvantageinstabilityandtherealizationofthemethodissimple,orderlyandinthesequenceofbasicobjectstobesortedrelativelyfewcases,directinsertionsortisthebestsort;generallyspeaking,noWhichsortisanabsoluteadvantageindifferentsituationsneedtoselecttheappropriatesortingmethod,ifnecessarytoachievethebestresultshavebeenmixed.

ThedemonstrationsystemconsistsofsortingalgorithmcalledC-completegraphwindowsAPIprogramming,brokenandsolidlineswithdatalinesandoperatinglinestransformthemobileinteractivedemotothetimertorefreshtheimageasabasetoachievedynamicpresentationoftheresults.Softwarecanalsoexportthedatainthesortingprocessandthesorteddata,andshowthecurrentsortmethodperformanceparameters,maximizingtheuser-friendlyhuman-computerinteractiondo.Rankingmethodinteachingsoftware,orhaveaverygoodlearningpurposes.【Keywords】ExchangedSortSelectionSortInsertionSortMergeSortSpacecomplexityTimecomplexitywindowsSDK

目录7289前言 4TOC\o"1-3"\h\u7289第一章排序算法的研究现状 53864第二章排序算法的实现方法及性能分析 7696第一节插入排序 713709一、直接插入排序 725441二、希尔排序 930882第二节交换排序 1118324一、冒泡排序 1111723二、快速排序 1217517第三节选择排序 147525一、直接选择排序 154568二、堆排序 1529857第四节归并排序 184429一、两路归并算法 187137二、归并排序 192895第五节各种排序算法的比较讨论 2115544第三章排序算法的动态演示 2325044第一节编程环境及语言 2323854一、编程环境的选择 239988二、编程语言和工具 2325089第二节动态演示程序界面实现 2417147一、界面及功能介绍 246125二、主界面的创建 2626723第三节排序算法动态演示实现 299291一、实现动态演示的方法 2922313二、实现动态演示步骤 2932640三、具体排序算法实现的过程 309628四、本章结束语 3228693结论 3319377致谢 3429558参考文献 3518760附录 3610656一、英文原文： 3618332二、英文翻译： 3717225三、源程序：(部分) 38第一章绪论第一节课题研究背景排序是计算机科学中最重要的研究问题之一,它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛的应用。由于它固有的理论上的重要性,2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序排列的。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一，这是因为具有相同关键码得数据元素，这些元素在排序结束中，它们之间的位置关系与排序前不能保持一致。排序算法是在整个计算机科学与技术领域上广泛被使用的术语。排序算法是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。在日常生活中经常需要对所收集到的各种数据信息进行处理，这些数据处理中经常用到的核心运算就是排序。例如图书管理员将书籍按照编号排序放置在书架上，方便读者查找；打开计算机的资源管理器，可以选择按名称、大小、类型等来排列图标。排序已被广泛应用在几乎所有的领域。在当今的计算机系统中，花费在排序上的时间占CPU运行时间的很大比重。有资料表明，在一些商用计算机上，用在排序上的CPU时间达到20%至60%。所以高效的排序算法是当今所需，而对现有的常用排序算法的性能分析和对比也有一定的作用。若对任意的数据元素序列使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称为排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。随着计算机技术的日益发展，其应用早已不局限于简单的数值运算。而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。排序算法的学习就是为以后利用计算机资源高效地开发非数值理的计算机程序打下坚实的理论、方法和技术基础。资料表明，在当今的计算机系统中，有50％以上的CPU时间是用在排序数据上的。目前人们已经提出了许多不同的排序算法，本文选择其中最基本也是最常用的一些算法进行讨论，介绍它们的基本思想和实现过程，分析各种算法的时间与空间复杂度，以清晰描述排序演示系统。作为计算机科学中一项复杂而重要的技术，排序一直是计算机领域内人们感兴趣的课题，寻找速度快、附加存储空间开销小的高效排序算法也一直是人们追寻的目标。本文讨论整数数组元素的排序，分析几种常见排序算法并进行比较。排序是程序设计中非常重要的内容，每一种程序设计语言中都涉及到排序，它的功能是将一组无序的数据序列变成有序的数据序列，结果一般只有两种情况：数据从大到小排列或者从小到大排列。排序的算法有很多种，常用的有三种，即冒泡排序、选择排序和插入排序。要判断排序算法的优劣，一般有两个标准：一是算法执行所需的时间，又称时间复杂度；二是算法所需的存储空间，又称空间复杂度。排序算法的优劣将直接影响到程序的性能。随着计算机技术的飞速发展，排序（Sorting）仍将成为计算机科学的一个重要组成部分。早期计算机多用于进行简单的数值计算，输入和输出的数据量不大，数据元素之间的关系较为简单，数据处理时间较长，但是自从第一台计算机诞生，随着操作系统从简单到复杂，从低级到高级的发展，排序速度也越来越快，当处理大批量数据，特别是成千上万的数据时，时间也挺长，但是效率已相当高了。操作系统大概经历了以下几个阶段：一、手工操作阶段；二、早期批量处理阶段；三、管理程序阶段；四、多道程序设计与多道批处理系统。有了这许多硬件和软件的支持，排序算法的实现就有了强大的支撑力，从而为我们的计算机科学注入了活力。计算机已经深入到人类社会的各个领域，其应用已经不再局限于科学计算，而更多用于控制，管理及数据处理等非数值计算的处理工作。另外，计算机加工处理的对象由纯粹的数值发展到字符，表格和图象等各种具有一定结构的数据，这就必须分析待处理对象的特性以及各处理对象之间存在的关系，而排序是其中必不可少的一份子。所以展望计算机世界，数据结构是它的支持框架，而作为数据结构中排序一大块，其作用是非同小可的。课题研究目的和意义排序分为两类：内部排序和外部排序。内部排序：是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外部排序：是指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外部排序。当然，本文则以内部排序为重点讨论。排序算法在日常生活中特别是计算机上有举足轻重的作用，如果没有好的排序算法，那么电脑会花费大量的时间在数据的查找上。本课题的研究则围绕几种基本的排序算法以及对其的动态演示为重心。在对排序算法的阐述中，对时下常用的排序算法从理论到实现进行了详细讲解。特别在实现过程中，采用C语言以函数的形式完成每一个排序方法的代码，方便移植。在第二章的最后还对每种排序方法的性能进行了分析以及对比，这样能让读者更深入的了解排序算法之间的关系以及在选择排序算法的过程中有一个明确的目标。本课题关于排序算法研究目的在于，本文收集并整理了时下常用的基本的排序方法，且对每种排序算法从讲解到代码的实现都很清晰，在读者对排序算法的学习或者教学过程中能启一定的参考作用。排序算法的动态演示程序则前所未有的用到了windowsSDK编程，这个十年前流行的技术现在早被MFC的光芒照耀，而前者本身在编程过程中就是对windows操作系统的学习以及对windows软件的底层运行机制的了解。论文的第三章也对整个编程过程进行了讲解，虽然重点在排序算法动态演示这块，但也对整个软件的运行过程进行了讲解，且运用了很多常用的控件，代码有很强的移植效果，从最后的演示结果来看，能让读者对排序算法有深入的认识。总而言之，本文对基本排序方法做了详细的总结，有很好的参考价值；演示程序则开先河的用了比较底层的图形编程，不但在运行速度上有所提高且演示效果明显易懂，对排序算法的教学和学习启很好的辅助作用。课题的主要工作和技术难点课题围绕排序算法展开，在理解每种算法后，则把主要工作集中在对各种排序算法的整理和代码实现以及动态演示程序的编写。在本文所讲述的排序算法中，都是基本的算法，所以资料比较丰富，学习过程中难点并不多。在选择题目以后，我一直把重点放在动态演示程序这一块，因为我适应不了MFC的编程机制，且我一直想学习win32编程并能通过这些对windows操作系统本身有所了解。我的参考资料则是经典的windows程序设计第五版，一本一千多页的书，我也是看了一大半惨对这种编程方法有初步了解其中包括对windows系统的了解，当然这个过程是枯燥乏味的。在看到第一个windows程序时是一头雾水，特别是里面的各种句柄真是让人晕头转向；还有CreateWindow里面的各种风格和扩展风格，加上控件的风格那可是多如牛毛；在windows系统上运行的软件，一开始需要注册窗口类，之后是创建窗口，刷新客户区，然后执行整个软件运行的最重要操作，消息处理函数。这个函数是一个回调函数，刚开始对回调函数的理解也是让人很痛苦的，但后来理解到回调函数就是不但软件要用且windows本身也要用到的一个函数，就是它实现了windows系统与在该系统上运行的软件之间的通信，简而言之，就是软件你要处理什么消息，自己去拿，系统都已经准备好了，剩下的你不需要的消息则由系统自己消化。一个十年前流行的技术本身资料很少，特别是最新的windows技术，所以很多地方都是很困难的。本课题几乎所以技术难点都集中在与编程这一块，包括排序算法的实现和软件的编写，而后者更显得沉重。后者范围太广且很多地方涉及到操作系统本身。一些知识之前根本没有接触过，都是遇到问题解决问题，可能这也是毕业设计的宗旨吧。

排序算法的实现方法及性能分析第一节插入排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。一、直接插入排序1.直接插入排序思想假设待排序数据存放在数组A[1..n]中（A[0]可用做监视哨），则A[1]可看作是一个有序序列，让i从2开始，依次将A[i]插入到有序序列A[1..i-1]中，A[n]插入完毕则整个过程结束，A[1..n]成为有序序列。排序过程示例（用“（）”表示有序序列）待排序数据：（25）548542119727315（n=10）i=2： （2554）8542119727315i=3： （82554）542119727315i=4： （8255454）2119727315i=5： （821255454）19727315i=6： （1821255454）9727315i=7： （182125545497）27315i=8： （1282125545497）7315i=9： （128212554547397）15i=10： （12815212554547397）排序结束3．算法实现可在数组中增加元素A[0]作为关键值（待插入的数据）存储器和循环控制开关。第i趟排序，即A[i]的插入过程为：①保存A[i]→A[0]②从后往前遍历，条件不符则数据后移③如果A[j]<=A[0]（即待排序的A[i]），则A[0]→A[j+1]，完成插入；否则，将A[j]后移一个位置：A[j]→A[j+1]；；继续执行③对于上面的数据实例，i从2依次变化到10的过程中，j值分别为{1，0，3，1，0，6，1，7，3}4．程序代码voidInsertSort(intA[],intn)//对数组A做直接插入排序{inti,j;for(i=2;i<n;i++)//A[0]用于待插数据存储，从第二个开始if(A[i]<A[i-1])//"<",需将A[i]插入有序子表 { A[0]=A[i];//复制到缓存充当哨兵 A[i]=A[i-1];//已经确定小于则用前值覆盖 for(j=i-2;A[0]<A[j];j--) A[j+1]=A[j];//接着前面，记录后移 A[j+1]=A[0];//插入到正确位置 }}5．算法分析（1）稳定性：稳定（2）时间复杂度：①原始数据正序，总比较次数：②原始数据逆序，总比较次数：③原始数据无序，第i趟平均比较次数=，总次数为：④可见，原始数据越趋向正序，比较次数和移动次数越少。（3）空间复杂度：仅需一个单元A[0]二、希尔排序希尔排序(Shell'sSort)又称“缩小增量排序”(DiminishingIncrementSort)，它也是一种属于插入排序类的方法，但在时间效率上较前述排序方法有较大的改进。1．基本思想任取一个小于n的整数S1作为增量，把所有元素分成S1个组。所有间距为S1的元素放在同一个组中。第一组：{A[1]，A[S1+1]，A[2*S1+1]，……}第二组：{A[2]，A[S1+2]，A[2*S1+2]，……}第三组：{A[3]，A[S1+3]，A[2*S1+3]，……}……第s1组：{A[S1]，A[2*S1]，A[3*S1]，……}先在各组内进行直接插人排序；然后，取第二个增量S2（<S1）重复上述的分组和排序，直至所取的增量St=1（St<St-1<St-2<…<S2<S1），即所有记录放在同一组中进行直接插入排序为止。增量序列可以有各种取法，但需要注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量必须等于1。排序过程示例设有10个待排序的记录，关键字分别为12,89,57,32,96,37,54,5,79,57，增量序列是5,3,2,1，希尔排序的过程如下表序号12345678910原始数据1289573296375457957S1=5组别①②③④⑤①②③④⑤排序结果1254532573789577996S2=3组别①②③①②③①②③①排序结果1254532573789577996S2=2组别①②①②①②①②①②排序结果5321237575479578996S4=1组别①①①①①①①①①①排序结果5123237545757798996表2_1_1其中相同组别内部执行直接插入排序，比如当S1=5时，同为①组的是12和37，同为②的是89和54……，这样的有五组分别在其内部进行直接插入排序，这里的第二组就变成了54和89，当所以的执行完，改变增量继续执行，直到增量等于1。所以越到后面整个序列越是有序，当然在基本有序的情况下，直接插入排序就会显得更简单。3．算法实现由于在分组内部使用的是直接插入排序，因此排序过程只要在直接插入排序的算法上对其步长进行修改就可以了，这里写了两个函数，一个调用一个实现了希尔排序，程序易于理解。4．程序代码voidShellPass(intA[],ints,intn)//对数组A进行一次希尔排序，增量为s{inti,j; for(i=s+1;i<n;i++) { A[0]=A[i];//设置监视哨兵 j=i-s; while(j>0&&A[0]<A[j])//前插条件满足 {A[j+s]=A[j];j=j-s;}//记录后移 A[j+s]=A[0];//插入正确位置 }}voidShellSort(intA[],intS[],intn,intt)//其中S为增量序列,n为数组长度{//按增量序列S[0…t-1],对顺序表L进行希尔排序inti;for(i=0;i<t;i++)ShellPass(A,S[i],n);}5．算法分析（1）稳定性：不稳定（2）时间复杂度：①希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得一种最好的增量序列，但大量的研究已得出一些局部的结论。如有人指出，当增量序列未时，希尔排序的时间复杂度为，其中t为排序趟数，。还有人在大量的实验基础上推出：当n在某个特定范围内，希尔排序所需要的比较和移动次数约为，当时，可减少到。②在直接插入排序中，数据越趋向于有序，比较和移动次数越少，希尔排序的目的则是增加这种有序趋势。虽然看起来重复次数较多，需要多次选择增量，但开始时，增量较大，分组较多，但由于各组的数据个数少，则比较次数累计值也小，当增量趋向1时，组内数据增多，而所有数据已经基本接近有序状态，因此，希尔排序的时间性能优于直接插入排序。空间复杂度：仅需一个单元A[0]第二节交换排序交换排序的基本思想是：两两比较待排序的数据，发现两个数据的次序相反则进行交换，直到没有反序的数据为止。一、冒泡排序1．冒泡排序的思想最多进行n-1趟排序，每趟排序时，从底部向上扫描，一旦发现两个相邻的元素不符合规则（如果由小到大排序，规则就是前者大于后者，由大到小则反之），则交换。我们发现，第一趟排序后，最小值在A[1]，第二趟排序后，较小值在A[2]，第n-1趟排序完成后，所有元素完全按顺序排列。排序过程示例（由小到大，从底部冒泡）待排序数据：5333195336382201939第一趟排序：3533319531963822039第二趟排序：3195333195320638239第三趟排序：3191953332053396382第四趟排序：3191920533339536382第五趟排序：3191920335339536382第六趟排序：3191920333953536382第七趟排序：没有反序数据，排序结束。3．程序代码voidBubbleSort(intA[],intn){//冒泡排序，从后往前遍历inti,j,flag=1;intTemp;//中间变量for(i=n;i>0&&flag==1;i--)//当flag=0时表示没有反序数列跳出循环，排序完毕{flag=0;//标志位 for(j=n-1;j>n-i;j--) if(A[j]<A[j-1])//不满足规则就交换 {flag=1;Temp=A[j]; A[j]=A[j-1];A[j-1]=Temp; }}}4．算法分析（1）稳定性：稳定（2）时间复杂度：①原始数据正序，需一趟排序，比较次数②原始数据反序，需n-1趟排序，比较次数③一般情况下，虽然不一定需要n-1趟排序，但由于每次数据位置的改变需要3次移动操作，因此，总时间复杂度高于直接插入排序。（3）空间复杂度：仅需一个中间变量Temp二、快速排序1．快速排序的思想在A[1..n]中任取一个数据元素作为比较的“基准”（不妨记为X），将数据区划分为左右两个部分：A[1..i-1]和A[i+1..n]，且A[1..i-1]≤X≤A[i+1..n](1≤i≤n)，当A[1..i-1]和A[i+1..n]非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。2．算法实现可以使用递归函数实现这一算法。假定待排序序列的下标范围为low~high。借用两个整型变量i、j作为指针，约定初值分别为low、high。排序过程：①选定基准X（不妨用A[low]）②j向前扫描，直到A[j]<X，交换A[i]与A[j]，i+1。保证了A[low..i-1]≤X③i向后扫描，直到A[i]>X，交换A[i]与A[j]，j-1。保证了X≤A[j..high]④继续执行②、③，直到i=j。这时，X恰好在A[i]位置上。⑤对序列A[low..i-1]及A[i+1..high]按照上述规律继续划分，直到序列为空。仔细分析算法，我们发现，在排序中，我们总是用基准X与另一数据交换，因此，一趟排序结束后，X就能确切定位其最终位置。3．排序过程示例待排序数据：6767145229990548771X=67ij扫描jij交换5467145229990678771扫描iij交换5467145229967908771j=i，结束ij第一趟排序后：54671452299[67]908771第二趟排序后：9291452[54]67[67]7187[90]第三趟排序后：[9]291452[54676771]87[90]第四趟排序后：[9]14[29]52[546767718790]第五趟排序后：[9142952546767718790]4．程序代码intPartition(intA[],intlow,inthigh){A[0]=A[low];//A[0]做哨兵，以它为界左右分开while(low<high){while(low<high&&A[high]>=A[0])//从数组的两端交替向中间扫描high--;A[low]=A[high];//将小于哨兵的数字移动到低端while(low<high&&A[low]<=A[0])low++;A[high]=A[low];//将大于哨兵的数字移动到高端}A[low]=A[0];//放置哨兵位returnlow;//返回其位置}voidQuickSort(intA[],intlow,inthigh){intcenter;//保存哨兵位置if(low<high){center=Partition(A,low,high);//将A[lowhigh]一分为二 QuickSort(A,low,center-1);//对低子表递归排序QuickSort(A,center+1,high);//对高子表递归排序}}5．算法分析（1）稳定性：不稳定（2）时间复杂度：每趟排序所需的比较次数为待排序区间的长度-1，排序趟数越多，占用时间越多。①最坏情况：每次划分选取的基准恰好都是当前序列中的最小(或最大)值，划分的结果A[low..i-1]为空区间或A[i+1..high]是空区间，且非空区间长度达到最大值。这种情况下，必须进行n-1趟快速排序，第i次趟去见长度为n-i+1，总的比较次数达到最大值：②最好情况：每次划分所取的基准都是当前序列中的“中值”，划分后的两个新区间长度大致相等。共需趟快速排序，总的关键字比较次数：。③基准的选择决定了算法性能。经常采用选取low和high之间一个随机位置作为基准的方式改善性能。（3）空间复杂度：快速排序在系统内部需要一个栈来实现递归，最坏情况下为，最佳情况下为，其中A[0]不记。第三节选择排序选择排序的基本思想是：每一趟从待排序的数据中选出最小元素，顺序放在已排好序的数据最后，直到全部数据排序完毕。一、直接选择排序1．过程模拟表2_3_1待排序数据92286284621656873366第一趟排序16286284629256873366第二趟排序16286284629256873366第三趟排序16283384629256876266第四趟排序16283356629284876266第五趟排序16283356629284876266第六趟排序16283356626284879266第七趟排序16283356626266879284第八趟排序16283356626266849287第九趟排序162833566262668487922．程序代码voidSelectSort(intA[],intn)//简单选择排序{inti,j;for(i=1;i<n;i++)//从前往后扫描 for(j=i+1;j<n;j++) if(A[i]>A[j])//小到大 { A[0]=A[i];//第i个记录和第j个记录交换 A[i]=A[j]; A[j]=A[0]; }}3．算法分析（1）稳定性：不稳定（2）时间复杂度：（3）空间复杂度：仅需一个中间单元A[0]二、堆排序1．堆排序思想堆排序是一种树形选择排序，在排序过程中，将A[1..n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。堆的定义n个元素的序列K1，K2，K3，…Kn称为堆，当且仅当该序列满足特性：Ki≤K2i，Ki≤K2i+1（1≤i≤n/2）堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列{1,35,14,60,61,45,15,81}就是一个堆，它对应的完全二叉树如下图1所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。图2_3_1最小堆图2_3_2最大堆堆排序过程（以最大堆为例）（1）调整堆假定待排序数组A为{20，12，35，15，10，80，30，17，2，1}（n=10），初始完全树状态为：图2_3_3图2_3_4结点（20）、（35）、(12)等，值小于其孩子结点，因此，该树不属最大堆。为了将该树转化为最大堆，从后往前查找，自第一个具有孩子的结点开始，根据完全二叉树性质，这个元素在数组中的位置为i=[n/2]，如果以这个结点为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。随后，继续检查以i-1、i-2等结点为根的子树，直到检查到整个二叉树的根结点（i=1），并将其调整为堆为止。调整方法：由于A[i]的左、右子树均已是堆，因此A[2i]和A[2i+1]分别是各自子树中关键字最大的结点。若A[i]不小于A[2i]和A[2i+1]，则A[i]没有违反堆性质，那么以A[i]为根的子树已是堆，无须调整；否则必须将A[i]和A[2i]与A[2i+1]中较大者（不妨设为A[j]）进行交换。交换后又可能使结点A[j]违反堆性质，同样由于该结点的两棵子树仍然是堆，故可重复上述的调整过程，直到当前被调整的结点已满足堆性质，或者该结点已是叶子结点为止。以上图为例，经过调整后，最大堆为：{80，17，35，12，10，20，30，15，2，1}。如图4_4所示。此堆作为排序的初始无序区。（2）选择、交换、调整①将建成的最大堆作为初始无序区。②将堆顶元素（根）A[1]和A[n]交换，由此得到新的无序区A[1..n-1]和有序区A[n]，且满足A[1..n-1]≤A[n]③将A[1..n-1]调整为堆。④再次将A[1]和无序区最后一个数据A[n-1]交换，由此得到新的无序区A[1..n-2]和有序区A[n-1..n]，且仍满足关系A[1..n-2]≤A[n-1..n]，同样要将A[1..n-2]调整为堆。直到无序区只有一个元素A[1]为止。说明：如果需要生成降序序列，则利用最小堆进行操作。4．程序代码voidmaxheapify(intA[],inti,intheapsize){intlargest,left,right,Temp;left=Left(i);right=Right(i);if(left<=heapsize&&A[left]>A[i])largest=left;elselargest=i;if(right<=heapsize&&A[right]>A[largest])largest=right;if(largest!=i){ Temp=A[i]; A[i]=A[largest]; A[largest]=Temp;maxheapify(A,largest,heapsize);}return;}voidHeapSort(intA[],intheapsize){inti,Temp;for(i=heapsize/2;i>=1;i--)/*buildmax-heap*/maxheapify(A,i,heapsize);for(i=heapsize;i>=2;i--)/*deletemax*/{Temp=A[1]; A[1]=A[i]; A[i]=Temp;heapsize--;maxheapify(A,1,heapsize);}}5．算法分析（1）稳定性：不稳定。假定数据序列为{1，1}，已是大堆，经过排序后，结果为{1，1}。（2）时间复杂度：堆排序的时间，主要由建立初始堆和反复调整堆这两部分的时间开销构成，它们均是通过调用maxheapify函数实现的。堆排序的最坏时间复杂度为。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。（3）空间复杂度：第四节归并排序归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。一、两路归并算法1、算法基本思路假设初始序列含有n个记录，则可看成是n个有序的子序列，没个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到一个长度为n的有序序列为止。设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为sr[left...mid]，sr[mid+1...right]，将它们归并为一个有序数列，并存储在sr[left...right]。2．程序代码voidMerge(int*sr,int*di,intleft,intmid,intright){//将有序的sr[left...mid]和sr[mid+1...right]归并为有序的di[left...right]inti=left,j=mid+1,k=left;while(i<=mid&&j<=right)//将sr中记录由小到大的并入di{if(sr[i]<sr[j])di[k++]=sr[i++];elsedi[k++]=sr[j++];}if(i>mid)//将剩余的sr[j...right]复制到diwhile(j<=right)di[k++]=sr[j++];elseif(j>right)//将剩余的sr[i...mid]复制到diwhile(i<=mid)di[k++]=sr[i++];}二、归并排序归并排序有两种实现方法：递归法和非递归方法。1．非递归法（1）基本思想自底向上的基本思想是：第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第1趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。上述的每次归并操作，均是将两个有序序列合并成一个有序序列，故称其为“二路归并排序”。类似地有k(k>2)路归并排序。（2）程序代码//归并排序之非递归voidMergeSort(intA[],intB[],intn){ intstep=1;//决定趟数 while(step<n) { MergePass(A,B,step,count);//#1 step=2*step; MergePass(B,A,step,count);//作用：和#1轮替执行，保证源数据是被部分归并过的； step=2*step;//作用：在归并完成后再调用一次，把最终归并结果copy到A数组中 }//其实是调用了MergePass里最后的for循环。}//归并排序非递归之一趟归并voidMergePass(intC[],intD[],intstep,intlen){//决定每一趟需要几次归并 inti=0; while(i<=len-2*step)//一组一组地进行归并（这两组是） { Merge(C,D,i,i+step-1,i+2*step-1); i+=2*step; } if(i+step<len)//如果剩余元素够一组再进行一次归并 Merge(C,D,i,i+step-1,len-1); else for(intj=i;j<=len-1;j++)//作用：如果元素不够一组那么直接把剩余元素copy到//目标指针所指向的空间 D[j]=C[j];//作用：一切元素都归并完成之后，把最终归并//结果copy到A数组中。}2．递归法采用递归法进行自顶向下的算法设计，形式更为简洁。（1）分治法的三个步骤设归并排序的当前区间是sr[l..h]，分治法的三个步骤是：分解：将当前区间一分为二，即求分裂点m=(l+h)/2；求解：递归地对两个子区间sr[l..m]和sr[m+1..h]进行归并排序；组合：将已排序的两个子区间sr[l..m]和sr[m+1..h]归并为一个有序的区间sr[l..h]。递归的终结条件：子区间长度为1（一个数据组成的区间必然有序）。（2）程序代码voidMSort(intsr[],di[],ints,intt){//将sr[s...t]归并到di[s...t]intm;if(s==t)di[s]=sr[s]; else { m=(s+t)/2;//将sr[s..t]平分为sr[s..m]和sr[m+1..t] MSort(sr,di,s,m);//递归的将sr[s..m]归并为有序的di[s..m] MSort(sr,di,m+1,t);//递归的将sr[m+1..t]归并为有序的di[m+1..t] Merge(sr,di,s,m,t);//将sr[s..m]和sr[m+1..t]归并为di[s..t] }}3．算法分析（1）稳定性归并排序是一种稳定的排序。（2）存储结构要求用顺序存储结构。也易于在链表上实现。（3）时间复杂度长度为n的数列，需进行趟二路归并，每趟归并的时间为，故其时间复杂度无论是在最好情况下还是在最坏情况下均是。（4）空间复杂度需要一个辅助数组来暂存两有序序列归并的结果，故其辅助空间复杂度为。第五节各种排序算法的比较讨论一、各种算法比较表2_5_1方法平均时间最坏所需时间空间复杂度稳定性直接插入排序稳定希尔排序不稳定简单选择排序不稳定堆排序不稳定冒泡排序稳定快速排序不稳定归并排序稳定主要内部排序算法的性能表从平均时间性能而言，快速排序最好，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较的结果是，在n较大是，归并排序所需要时间较堆排序省，但它所需的辅助存储量最多。在时间复杂度为的排序算法（直接插入排序、简单选择排序、冒泡排序），其中直接插入排序最为简单，当序列中的记录“基本有序”或者n值较小时，它是最佳的排序方法，因此常将它和其他的排序方法，如快速排序、归并排序等结合在一起使用。从方法的稳定性来比较，所有时间复杂度为的排序方法都是稳定的，然而快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。一般来说，排序过程中的“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。值得提出的是，稳定性是由方法本身决定的，对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来。反之，对稳定的排序方法，总能找到一种引起不稳定的描述形式。由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行，则应根据问题所需慎重选择排序方法及其描述算法。二、选取排序算法的主要因素◆待排序的记录数目n；◆每个记录的大小；◆关键字的结构及其初始状态；◆是否要求排序的稳定性；◆语言工具的特性；◆存储结构的初始条件和要求；◆时间复杂度、空间复杂度和开发工作的复杂程度的平衡点等。综上所述，在本章讨论的所用排序方法中，没有那一种排序算法是绝对最优的。有的适用于n较大的情况，有的适合于n较小的情况，有的………因此，在实用时需要根据不同情况适当选用，甚至可将多种方法结合起来使用。第三章排序算法的动态演示第一节编程环境及语言一、编程环境的选择现在比较流行的有MicrosoftVisualStudio2008和MicrosoftVisualC++6.0，前者界面很人性化，对工程和代码的管理做得很好，有强大智能提示功能和接近完美的MSDN帮助文件，后者对代码的兼容性很高，几乎前十几年的windowsC/C++代码都是用它编写的，所以在程序的参考和编译来看，它无可挑剔，但是那些粗糙的界面也很是让人枯燥。本程序编译环境是MicrosoftVisualStudio2008，在所以VS系列中是最稳定，应用最广的一个版本。二、编程语言和工具MFCObject:MFC(MicrosoftFoundationClasses)，是一个微软公司提供的类库（classlibraries），以C++类的形式封装了Windows的API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。其中包含的类包含大量Windows句柄封装类和很多Windows的内建控件和组件的封装类。MFC是微软封装了的API。windows作为一个提供功能强大的应用程序接口编程的操作系统，的确方便了许多程序员，传统的win32开发（直接使用windows的接口函数API）对于程序员来说非常的困难，因为，API函数实在太多了，而且名称很乱，从零构架一个窗口动辄就是上百行的代码。MFC是面向对象程序设计与Applicationframework的完美结合，他将传统的API进行了分类封装，并且为你创建了程序的一般框架。确定，对于初学者很难理解它的后台运行机制。windowsAPIObject:视觉操作系统应用程序接口（windowsAPI），有非正式的简称为WinAPI，是微软对于windows操作系统中可用的核心应用程序编程接口的称法。它被设计为各种语言的程序调用，也是应用软与windows系统的最直接交互方式。WindowsAPI为程序员提供大量的构建不同windows的底层结构，这有助于为windows程序员开发应用程序提供大量的灵活性和功能。但是，它同样是windows应用程序要负责处理大量底层且又是是繁琐的与图形用户界面（GUI）相关的操作。虽然题目是要求用MFC编写，但我还是选择了windowsAPI编程，应为我觉得前者有很多东西我很难理解，还有自己对C++没有深刻的认识，对类封装这一新接触概念很难接受，对MFC后台的运行机制并不明白。而winAPi则不同，全部采用C语言对windowsAPI进行调用，从WinMain进入主函数，到CALLBACKWndProc回调到消息处理函数，整个过程思路很清晰，只是在图形编程上有些繁琐而已，对消息的接收和处理反复操作，就连改变一个字体都要通过消息发送，但经过几个月的学习，已经能熟练的建立图形界面和操作消息了。以下就是我的演示程序的编写过程及细节。第二节动态演示程序界面实现一、界面及功能介绍1、主界面：图3_2_1模块说明主程序用groupbox控件把程序分为若干个模块：演示区、操作区、排序方法、调速、风格、颜色和数据查看。这样做的好处是让界面看上去清晰整洁。（1）演示区这是整个程序最重要的模块。当未进入演示阶段时，演示区TextOut打印出演示规则及相关说明，如图2_2_1所示；进入演示画面时如图2_2_2，（直接插入排序）红色的线条是操作线，其他是数据线，当遇到需要移动的数据线，其会改变为虚线，然后移动到适当的位置，整个演示就是这样的寻找排序过程；当排序完成如图2_2_3，界面会显示整个过程的比较次数和移动次数。图3_2_2图3_2_3（2）操作区第一个按键点击后程序会运行随机产生数组randpoint[143]，并用背景刷刷掉演示区，然后绘制数据线条和操作线条。这里要注意的是，每次需要观看演示程序的时候，第一步一定得先创建数据，因为这个消息函数里面涉及到一些图像以及函数的初始化工作；之后可以点击开始，当然途中也可以暂停和继续。（3）排序方法该模块包括内容有排序方法的选择，这里用到了列表框，还有就是对该排序方法的一些性能说明，其中有稳定性、时间复杂度、空间复杂度。当用户选择了一种新的排序方法时，在观看演示之前一定要创建数据，这里再次说明。（4）调速、风格和颜色区调速左慢右快，具体是通过slider控件产生1~1000的整数，然后对定时器进行设置；风格就是可以选择数据线或者数据点，当然是二选一，还有就是可以去除操作线（这里存在一定的bug）；颜色区就不用多说了，可以改变背景颜色和数据线颜色，操作线颜色就没有提供修改方案，这些都是画刷的一些选择操作，程序并没有把过多精力放在上面。（5）数据查看这个区域比较重要，当点击按键是程序会产生一个与之对应的对话框，里面会把操作数据全部TextOut。用户可以在创建数据后查看原始数据，还可以在排序过程中查看部分已排序的数据，这些只需要点击“过程数据”按键就ok，如图3_2_4所示。如果想查看已经排序成功的数据，那么点击“排序数据”按键就会弹出列好从小到大的数据，如图3_2_5所示。这里要说明的是，随机产生的数范围是0~280，至于为什么，这个是根据演示区的高度像素点决定的，还有就是演示用的随机数组，和完成排序数据的数组是分开的，所以才能实现二者的独立性，并不互相干扰，但是为了数据的统一，数据还是不要随便创建。图3_2_4图3_2_5二、主界面的创建在程序入口主函数WinMain里面定义了结构体wndclass，然后注册窗口类，也就是对结构体内部元素的填充，参数差不多都选择默认，只是图标MAKEINTRESOURCE了我自己添加到资源的一个图标（自动化四班班徽）；如果窗口注册成功，那么就开始CreatWindow，这里我创建了一个宽600像素点，高470像素点的窗口，风格默认。差不多主界面就创建完成，后面ShowWindow和UpdateWindow显示窗口并刷新客户区，然后就是进入消息循环直到窗口关闭。这里不得不提几个比较重要的变量：hInst=hInstance，窗口实例句柄，这里传给全局变量hInst，方便以后的操作；hwnd，就是创建主窗口返回的主窗口句柄，这个很重要，很多依赖主窗口所创建的控件都要用到这个句柄，包括对主窗口客户区的操作也必须hdc=GetDC(hwnd)来获得客户区句柄。各个模块的具体实现1、所有控件清单7个groupbox控件：负责对每个模块区分画界限，是软件界面一目了然；5个button控件：就是按键，三个负责操作，另外两个调用两个对话框；3个combobox控件：列表框控件，一个是算法的选择，后两个分别是对背景和数据线颜色的设置；2个radiobutton控件和1个checkbox控件：用于风格操作，radiobutton只能二选一，checkbox可选可不选；1个slider控件：滑块控件，用于速度调节的；8个static控件：5个静态字体用于具体说明，另外3个是算法性能参数，根据算法不同会有相应的值。1个灰色框：包围演示区，有界限美观作用；2个dialog对话框：一个是过程数据，一个是排序后数据。2、控件的创建这里由一个button控件为例：hpushbutton=CreateWindow(TEXT("button"),TEXT("创建数据"),WS_CHILD|WS_VISIBLE|BS_PUSHBUTTON,32,377,56,32,hwnd,(HMENU)IDM_BUILD_DATA,hInst,NULL);容易看出还是由CreatWindow（……）函数完成，其中第一个参数和第三个参数的BS_PUSHBUTTON决定了它的控件类型；第二个参数是控件名字，风格则表示创建的是控件而且visible就是可视的；后面的数字，前两个表示开始的x、y坐标，后者表示宽高；再后来是主窗口句柄，IDM_BUILD_DATA是控件ID，在消息处理函数的WM_COMMAND消息下由wParam参数的低字节传递；最后是实例句柄和扩展，就不多说。函数返回hpushbutton控件的当前句柄，用于对控件的设置等，由SendMessage函数完成。关于控件字体的修改，因为系统默认的字体实在难看，所以就自己创建了一个字体类，定义属性为宋体，12号，SendMessage(hgroupbox,WM_SETFONT,(WPARAM)hfont,TRUE)来实现修改字体，其中hfont就是创建的字体类。其他控件大体都是这样创建的，根据控件的不同或者需求不同，可以有不同的风格和创建方式，以及后来微软提供的CreatWindowEx函数更能增加控件的美观性，当然也可以手动绘制控件等，在这里就不多讨论。重要地说一点是，关于滑块控件的使用，它是控件里面最特别的一个，其它的控件ID都由WM_COMMAND消息下传递，而滑块控件是单独的消息，根据横向或者纵向有WM_HSCROLL和WM_VSCROLL消息。3、关于dialog对话框的创建首先是在资源视图里面创建一个newdialog，然后设置其ID，其消息的传回跟上面的其他普通控件一样。差不多创建就完成，之后要做的就是连接，和其自身内部的消息处理，对话框其实就想一个对立的窗口一样，它有自己的消息体，所以需要想主窗口那样建立一个消息回调函数，然后在主消息循环里面添加如下代码：DialogBox(hInst,MAKEINTRESOURCE(IDD_DIALOG2),hwnd,AboutDlgProc);其中最后一个参数就是他自己的消息回调函数,比如一个简单的回调函数如下：BOOLCALLBACKAboutDlgProc(HWNDhDlg,UINTmessage,WPARAMwParam,LPARAMlParam){ switch(message) { caseWM_INITDIALOG: returnTRUE; caseWM_COMMAND: switch(LOWORD(wParam)) { caseIDOK: EndDialog(hDlg,0); break; } break; } returnFALSE;}WM_INITDIALOG接受对话框的初始化，有点像主消息函数里面的WM_CREATE，WM_COMMAND消息的wParam参数的地位字是默认按钮的ID。本例中该ID是IDOK，就是OK键。点击EndDialog(hDlg,0)接受对话框。第三节排序算法动态演示实现一、实现动态演示的方法就像动画一样，一定时间更换一张图片，就实现了动画的连续性，那就是动态的。所以对于简单的图形动态编程，可以以定时器为核心，因为定时器每到一个规定时间就会产生WM_TIMER消息。在接收到这一消息时，我们要做的就是，擦除以前的图形，画出新的图形，这样反复操作就实现了动态演示。在进入定时器之前，必须对图形进行初始化，做好一切准备工作，因为一旦程序开始接收WM_TIMER消息，它就只会做两件事情，一是擦图像，二是画图像，直到排序完成。这里需要说明的是，整个演示程序只代表性的选择了三个排序算法：简单选择排序、直接插入排序和冒泡排序。因为上一章已经对常用的排序算法有了深刻的讲解，所以并没有全部都实现了动态演示。二、实现动态演示步骤1.准备当用户点击“创建数据”按钮，程序要做的就是：（1）把演示区用背景刷刷成背景色（2）RandomData(randpoint,143)产生随机数组（3）一个for循环把随机数组对应的值绘制成线，由下往上绘制（4）选择排序算法初始化：这里的iIndex值就是combobox列表框控件产生的switch(iIndex)//排序方法选择 { case0:BubbleInit(hdc);//冒泡 break; case1:InsertInit(hdc);//直接插入 break; case2: SelectInit(hdc);//选择排序 break; }2.开始当消息接收到WM_COMMAND消息里的IDM_PLAY（“开始”按钮的ID）时，执行代码：SetTimer(hwnd,1,speed,NULL)就是建立一个定时器，定时时间是speed，这个参数由slider速度控件产生。当定时器一设置后，系统就会产生WM_TIMER消息，之后要做的就是去接收这个消息，反复在里面改变图像。3.运行caseWM_TIMER: switch(iIndex) { case0:BubbleSort(hdc);//冒泡排序 break; case1:InsertSort(hdc);//直接插入 break; case2: SelectSort(hdc);//简单选择排序 break; }return0;表面看很简单，其实这是整个程序的精髓，只不过用函数封装了显得简单。当排序完成，这里还有关闭KillTimer定时器，还有告诉用户这个排序一共比较多少次，移动了多少次。三、具体排序算法实现的过程以下将以直接插入排序和简单选择排序为例子讲解具体排序算法的实现：1.直接插入排序算法第二章已经详细的讲了直接插入排序算法的实现过程，简而言之就是，待排序数据挨个从后向前和前面已排序数据比较，如果满足比较条件则插入，后面的依次后移。这样反反复复直到完成。程序的最开始构建了两个POINT点数组ptlast[4]和ptnow[4]用于操作线（红色）的更新和保存，因为操作线由一条折线组成，所以需要4个点，然后用Polyline函数完成绘制。直接插入排序里面的操作线是这样布置的，始端指向和待排序数据长度一样的克隆线条，如果数据不是待排序数据则指向上一次的待排序数据；末端指向需要处理的数据，当然这个数据不一定是待排序数据，如果是则会马上被绘制为虚线，不是的话则不变。进入InsertSort函数后，第一件事就是擦除上次的操作线，然后会进入一个大的if语句，这里是因为我设置了一个标志位sign，它的作用把定时器再次分为两次操作，其赋值为01变换。当sign=1时，操作线指向下一数据，如果满足待排序条件，这里条件就是其值小于前面数据值，满足条件情况下，就将其画成虚线，表示即将对其进行插入操作。然后更新ptnow[4]，调整操作线，具体如图3_3_1所示。当sign=0时，就是排序的关键了，如果数据满足待排序原则，那么用一变量储存当前值，之后从后往前遍历，遇到比关键字大的数据就后移，一直反复操作，直到找到合适位置，停止移动，把关键字插入到该位置，继续让其成虚线状，这能让用户直观的观察到具体的插入位置，如下图的图3.3.1。图3.3.1图3.3.2程序跳出if语句后，会对sign进行切换操作，还有操作线数据点的保存，以便下次进入时擦除它。这样一次操作就算完成，通过countx++，实现向后连续操作，通过它耶可以判断是否排序完成。2.简单选择排序与直接插入排序所不同的是，操作线会跟随正在做比较的两根数据线，如果遍历到的数据线需要交换就会被画为虚线。为排序前数据如图3_3_3所示，很容易看出所有数据里面间夹着小数据量，好像缝隙一样。随着排序的进行这样的情况会越来越少，如图3_3_4，因为小数据都被一个一个交换到前面去了，后面的数据参差愈是小，这就是选择排序的原理，一次一次地寻找最小的数据交换到前面。图3.3.3图3.3.4四、本章结束语由实际效果来看，采用数据线和操作线的动态演示是可行的，能直观的演示整个排序过程，而且程序还提供了过程数据和排序后的数据参考，图像和数字结合的观察效果还是很好的，在排序算法教学或者理解上能有很大的帮助。结论目标在现代信息技术的高速发展,实际工程应用基本都面临着大量的无序信息。若没有排序算法，大量的时间将花费在数据查找过程。因此，高效的排序算法在工程应用中具有重要的意义。本课题在对数据结构和算法分析理论的了解的基础上，通过学习多种排序算法（选择