《数据结构与算法》课程设计成果报告-排序算法实现.doc

河南工程学院数据结构与算法课程设计成果报告排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4算法比较分析72.5 程序流程图82.6 测试程序说明93 程序清单104 测试164.1 测试数据164.2 测试结果分析165 总结18参考文献191 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计排序相关函数库，以便在程序设计中调用，要求设计程序完成下面功能：（1）对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序，并把排序结果进行保存；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的求解。2 分析与设计2.1 题目实现步骤为了实现题目要求：（1）先理解程序的功能，知道并会利用排序的核心算法。（2）首先设计数据的存储结构，构建程序框架，设计程序流程图如图。（3）实现程序的功能模块，完成程序的调试。2.2 存储结构设计在排序的过程中需要以下两种操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。前一个操作对大多数的算法都是必要的，而后一个操作可以通过改变记录的存储方式来实行。待排序的记录序列可有三种存储方式：（1）待排序的一组记录存放在地址连续的一组存储单元上。它类似于线性表的顺序存储结构，在序列中相邻的两个记录，他们的存储位置也相邻。在这种存储方式中，记录之间的次序关系由其存储位置决定，实现排序必须借助移动记录；（2）待排序的一组记录存放在静态链表中，记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针即可；（3）待排序记录本身存储在一组地址连续的存储单元内，同时令设一个指示各个记录存储位置的地址向量，在排序过程中不需要移动记录本身。，而移动地址向量中这些记录的“地址”，在排序结束之后在安照地址向量中的值来调整记录的存储位置。在以下设计的算法中，待排记录的数据类型为：#define MAXSIZE 20 / 一个用作示例的小顺序表的最大长度typedef int KeyType; / 定义关键字类型为整型typedef int InfoType; / 定义其它数据项的类型struct RedType / 记录类型KeyType key; / 关键字项InfoType otherinfo; / 其它数据项，具体类型在主程中定义;struct SqList / 顺序表类型RedType rMAXSIZE+1; / r0闲置或用作哨兵单元int length; / 顺序表长度;2.3 算法描述（1）直接插入排序这是一种最简单的排序方法，基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增一的有序表。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，最坏时间复杂性为O(n2)，空间复杂度为O(1)。【例】关键字为49 38 65 97 76 13 27 49 则直接插入做法如图2-1初始关键字 （49） 38 65 97 76 13 27 49I=2； （38） （38 49）65 97 76 13 27 49I=3； （65） （38 49 65）97 76 13 27 49I=4； （97） （38 49 65 97）76 13 27 49I=5； （76） （38 49 65 76 97） 13 27 49I=6； （13） （13 38 49 65 76） 97 27 49I=7； （27） （13 27 38 49 65 76 97）49I=8； （49） （13 27 38 49 49 65 76 97 ） 监视哨L.r0图2-1直接插入法示例直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。（2）折半插入排序它是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为alow，末元素设置为ahigh，则轮比较时将待插入元素与am，其中m=(low+high)/2相比较,如果比参考元素小，则选择alow到am-1为新的插入区域(即high=m-1)，否则选择am+1到ahigh为新的插入区域（即low=m+1），如此直至low=high不成立，即将此位置之后所有元素后移一位，并将新元素插入ahigh+1。（3）希尔排序希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DLShell于1959年提出而得名。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量=1(d2d1)，即所有记录放在同一组中进行直接插入排序为止。（4）冒泡排序算法冒泡排序算法的运作如下：（从后往前）比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。（5）快速排序快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（6）归并排序归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并过程为：比较ai和aj的大小，若aiaj，则将第一个有序表中的元素ai复制到rk中，并令i和k分别加上1；否则将第二个有序表中的元素aj复制到rk中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间s,t以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间s,t。（7）堆排序堆排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。n个关键字序列Kl，K2，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：大根堆示例(1)ki=k(2i）且ki=号。/k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点。将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。【例】关键字序列（10，15，56，25，30，70）和（70，56，30，25，15，10）分别满足堆性质（1）和（2），故它们均是堆，其对应的完全二叉树分别如图2-3根堆示例和大根堆示例所示。101556253070101556253070705630251510705630251510图2-3堆示例和大根堆示例大根堆和小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。堆的高度：高度堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）。（8）简单选择排序设所排序序列的记录个数为。i取1,2,n-1,从所有n-i+1个记（R,Ri+1,Rn中找出排序码最小的记录，与第个记录交换。执行n-1趟 后就完成了记录序列的排序。在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。 最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+2+1=n(n-1)/2，即进行比较操作的时间复杂度为 O(n2)。2.4算法比较分析算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。因此我们可以通过比较这几个算法的时间复杂度，来选择最适合的算法。这几种排序算法比较如图2-4：图2-4 算法比较分析2.5 程序流程图将所有的排序方法，打包成函数并设计实现相应的函数接口，方便在Main函数中调用。设计存储结构，实现排序算法，通过调用函数对测试数据进行排序，并输出结果。按照编程思想，实现相应的程序，程序流程图如图2-5：开始初始化构建存储表调用折半排序算法调用简单选择排序算法调用希尔排序算法调用直接插入排序算法调用起泡算法调用快速排序算法调用归并排序算法调用堆排序算法调用排序函数调用print函数，输出结果结束图2-5 程序流程图2.6 测试程序说明程序测试：根据自己的程序，在主程序中设定相应的函数操作，通过函数接口调用相应的函数对自己建立的顺序表进行排序，并在屏幕显示相应的结果。#include#include / malloc()等#include / EOF(=Z或F6),NULL#define LQ(a,b) (a)=(b)void main()SqList l1,l2,l3,l4,l5,l7,l8,l9;/定义顺序表int i;for(i=0;iN;i+) / 给l1.r赋值l1.ri+1=di; l1.length=N;l9=l8=l7=l5=l4=l2=l3=l1; printf(排序前:n); print(l1);InsertSort(l1); printf(直接插入排序后:n); print(l1);BInsertSort(l2); printf(折半插入排序后:n); print(l3);printf(进行希尔排序:n); int dt3=5,3,1; ShellSort(l4,dt,3); printf(排序后:n ); print(l4);SelectSort(l5); printf(简单选择排序后:n); print(l5);MergeSort(l7);printf(归并排序后:n); print(l7);QuickSort(l8); printf(快速排序后:n); print(l8);bubble_sort(l9); printf(冒泡排序后:n); print(l9);3 程序清单void InsertSort(SqList &L) / 对顺序表L作直接插入排序。int i,j;for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key) / ,需将L.ri插入有序子表L.r0=L.ri; / 复制为哨兵for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj; / 记录后移L.rj+1=L.r0; / 插入到正确位置void BInsertSort(SqList &L) / 对顺序表L作折半插入排序。int i,j,m,low,high;for(i=2;i=L.length;+i)L.r0=L.ri; / 将L.ri暂存到L.r0low=1;high=i-1;while(low=high+1;-j)L.rj+1=L.rj; / 记录后移L.rhigh+1=L.r0; / 插入void print(SqList L)int i;for(i=1;i=L.length;i+)printf(%d,%d),L.ri.key,L.ri.otherinfo);printf(n);void ShellInsert(SqList &L,int dk) / 对顺序表L作一趟希尔插入排序。int i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj; / 记录后移，查找插入位置L.rj+dk=L.r0; / 插入void ShellSort(SqList &L,int dlta,int t) / 按增量序列dlta0.t-1对顺序表L作希尔排序。int k;for(k=0;kt;+k)ShellInsert(L,dltak); / 一趟增量为dltak的插入排序printf(第%d趟排序结果: ,k+1);print(L);int SelectMinKey(SqList L,int i) / 返回在L.ri.L.length中key最小的记录的序号KeyType min;int j,k;k=i; / 设第i个为最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) / 找到更小的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) / 对顺序表L作简单选择排序。int i,j;RedType t;for(i=1;iL.length;+i) / 选择第i小的记录，并交换到位j=SelectMinKey(L,i); / 在L.ri.L.length中选择key最小的记录if(i!=j) / 与第i个记录交换t=L.ri;L.ri=L.rj;L.rj=t;void Merge(RedType SR,RedType TR,int i,int m,int n) / 将有序的SRi.m和SRm+1.n归并为有序的TRi.n int j,k,l;for(j=m+1,k=i;i=m&j=n;+k) / 将SR中记录由小到大地并入TRif LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;if(i=m)for(l=0;l=m-i;l+)TRk+l=SRi+l; / 将剩余的SRi.m复制到TRif(j=n)for(l=0;l=n-j;l+)TRk+l=SRj+l; / 将剩余的SRj.n复制到TRvoid MSort(RedType SR,RedType TR1,int s, int t) / 将SRs.t归并排序为TR1s.t。int m;RedType TR2MAXSIZE+1;if(s=t)TR1s=SRs;elsem=(s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMSort(SR,TR2,s,m); / 递归地将SRs.m归并为有序的TR2s.mMSort(SR,TR2,m+1,t); / 递归地将SRm+1.t归并为有序的TR2m+1.tMerge(TR2,TR1,s,m,t); / 将TR2s.m和TR2m+1.t归并到TR1s.tvoid MergeSort(SqList &L) / 对顺序表L作归并排序。MSort(L.r,L.r,1,L.length); int Partition(SqList &L,int low,int high) / 交换顺序表L中子表rlow.high的记录，枢轴记录到位，并返回其/ 所在位置，此时在它之前（后）的记录均不大（小）于它。KeyType pivotkey;L.r0=L.rlow; / 用子表的第一个记录作枢轴记录pivotkey=L.rlow.key; / 枢轴记录关键字while(low high) / 从表的两端交替地向中间扫描while(low=pivotkey)-high;L.rlow=L.rhigh; / 将比枢轴记录小的记录移到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow; / 将比枢轴记录大的记录移到高端L.rlow=L.r0; / 枢轴记录到位return low; / 返回枢轴位置void QSort(SqList &L,int low,int high) / 对顺序表L中的子序列L.rlow.high作快速排序。算法10.7int pivotloc;if(lowhigh) / 长度大于1pivotloc=Partition(L,low,high); / 将L.rlow.high一分为二QSort(L,low,pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high); / 对高子表递归排序void QuickSort(SqList &L) / 对顺序表L作快速排序。QSort(L,1,L.length); void bubble_sort(SqList &l,int n) / 将a中整数序列重新排列成自小至大有序的整数序列(起泡排序)int i,j;RedType t;for(i=0;i0;j-)if(l.rj.keyO(log2n) O(n)； 其它排序方法归为一类，其空间复杂性为O(1)。 （3） 稳定性 所有排序方法可分为两类，一类是稳定的，包括直接插入排序、起泡排序、简单选择排序和归并排序；一类是不稳定的，包括希尔排序、快速排序和堆排序。 （4） 算法简单性 从算法简单性看，一类是简单算法，包括直接插入排序、简单选择排序和起泡排序；另一类是改进算法，包括希尔排序、堆排序、快速排序和归并排序。 （5） 记录本身信息量的大小 记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。因此数据较多时应选择快速排序、堆排序、归并排序。 （6） 关键码的分布情况当待排序记录序列为正序时，直接插入排序和起泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)； 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。因此关键码的分布也是选择排序方法时的重要因素。5 总结在这次编程中，我完成了对数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、2-路归并排序的程序。由于个人能力不足，未完整的完成老师的题目要求，没有实现堆排序的算法和未实现数据操作后的输出保存工作。不过通过具体的上机实验，我自己发现了自己在编程中的许多问题，也发现了自己在学习中的问题所在，通过老师的指导和同学的帮助，自己完成了老师所布置的任务，更在具体的实现过程中，复习了数据结构的排序算法基础知识，填补了自己在平时学习中的漏洞。参考文献1吴伟民.数据结构（C语言版）.清华大学出版社2吴永辉等.数据结构编程实验（第二版）.机械工业出版社3徐子珊.算法设计、分析与实现（第三版）.人民邮电出版社4刘振宇.数据结构（C语言版）.东软电子出版社5张乃孝.算法与数据结构（第二版）.高等教育出版社#include#include / malloc()等#include / EOF(=Z或F6),NULL#define LQ(a,b) (a)=(b)#define MAXSIZE 20 / 一个用作示例的小顺序表的最大长度typedef int KeyType; / 定义关键字类型为整型typedef int InfoType; / 定义其它数据项的类型struct RedType / 记录类型KeyType key; / 关键字项InfoType otherinfo; / 其它数据项，具体类型在主程中定义;struct SqList / 顺序表类型RedType rMAXSIZE+1; / r0闲置或用作哨兵单元int length; / 顺序表长度;/直接插入排序void InsertSort(SqList &L) / 对顺序表L作直接插入排序。int i,j;for(i=2;i=L.length;+i)if LT(L.ri.key,L.ri-1.key) / ,需将L.ri插入有序子表L.r0=L.ri; / 复制为哨兵for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj; / 记录后移L.rj+1=L.r0; / 插入到正确位置/折半插入排序void BInsertSort(SqList &L) / 对顺序表L作折半插入排序。int i,j,m,low,high;for(i=2;i=L.length;+i)L.r0=L.ri; / 将L.ri暂存到L.r0low=1;high=i-1;while(low=high+1;-j)L.rj+1=L.rj; / 记录后移L.rhigh+1=L.r0; / 插入/ 2_路插入排序void P2_InsertSort(SqList &L) / 2_路插入排序int i,j,first,final;RedType *d;d=(RedType*)malloc(L.length*sizeof(RedType); / 生成L.length个记录的临时空间d0=L.r1; / 设L的第1个记录为d中排好序的记录(在位置0)first=final=0; / first、final分别指示d中排好序的记录的第1个和最后1个记录的位置for(i=2;i=L.length;+i) / 依次将L的第2个最后1个记录插入d中if(L.ri.keydfinal.key) / 待插记录大于d中最大值，插到dfinal之后(不需移动d数组的元素)final=final+1;dfinal=L.ri;else / 待插记录大于d中最小值，小于d中最大值，插到d的中间(需要移动d数组的元素)j=final+; / 移动d的尾部元素以便按序插入记录while(L.ri.keydj.key)d(j+1)%L.length=dj;j=(j-1+L.length)%L.length;dj+1=L.ri;for(i=1;i=L.length;i+) / 把d赋给L.rL.ri=d(i+first-1)%L.length; / 线性关系void print(SqList L)int i;for(i=1;i=L.length;i+)printf(%d,%d),L.ri.key,L.ri.otherinfo);printf(n);/希尔插入排序void ShellInsert(SqList &L,int dk) / 对顺序表L作一趟希尔插入排序。int i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj; / 记录后移，查找插入位置L.rj+dk=L.r0; / 插入void ShellSort(SqList &L,int dlta,int t) / 按增量序列dlta0.t-1对顺序表L作希尔排序。int k;for(k=0;kt;+k)ShellInsert(L,dltak); / 一趟增量为dltak的插入排序printf(第%d趟排序结果: ,k+1);print(L);/简单选择排序int SelectMinKey(SqList L,int i) / 返回在L.ri.L.length中key最小的记录的序号KeyType min;int j,k;k=i; / 设第i个为最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) / 找到更小的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) / 对顺序表L作简单选择排序。int i,j;RedType t;for(i=1;iL.length;+i) / 选择第i小的记录，并交换到位j=SelectMinKey(L,i); / 在L.ri.L.length中选择key最小的记录if(i!=j) / 与第i个记录交换t=L.ri;L.ri=L.rj;L.rj=t;/堆排序/*void HeapAdjust(SqList &l,int s,int m) / 已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，本函数/ 调整H.rs的关键字,使H.rs.m成为一个大顶堆(对其中记录的关键字而言)RedType rc;int j;rc=l.rs;for(j=2*s;j=m;j*=2) / 沿key较大的孩子结点向下筛选if(j0;-i) / 把H.r1.H.length建成大顶堆HeapAdjust(l,i,l.length);for(i=l.length;i1;-i) / 将堆顶记录和当前未经排序子序列H.r1.i中最后一个记录相互交换t=l.r1;l.r1=l.ri;l.ri=t;HeapAdjust(l,1,i-1); / 将H.r1.i-1重新调整为大顶堆*/归并排序vo