山东大学《数据结构》讲义07排序.docx

第七章排序
内容概述：
我们居住在一个迷惑于如何保存信息的世界里，为了寻找出路，人们必须以某 种切合实际的顺序来保存信息。本章我们考虑数据处理中经常遇到的问题一排 序，主要内容包括：排序的基本概念；插入排序、交换排序、堆排序、归并排序 等内排序方案及实现算法；外排序简介。
重点与难点：
重点为插入、交换、选择等基本排序方法和改进的排序方法，归并排序算法及基 数排序算法。
难点为快速排序算法、堆排序算法和归并排序算法。
思考与习题：
1 .从时间复杂度的角度对排序方法进行归类。
2 .在所有排序方法中，关键字比拟的次数与记录的初始排列次序无关有哪些？
3 .空间复杂度最正确的排序方法有哪些？
4 .从算法的简单性角度对排序方法进行归类.序列{503, 17, 512, 908, 170, 897, 275, 653, 426, 154, 509,
612, 677, 765, 703, 94},请给出采用希尔排序法（dl=8）对该序列作升序 排序时的每一趟的结果。
5 .序列{70, 83, 100, 65, 10, 32, 7, 9},请给出采用插入排序法对该 序列作升序排序时的每一趟的结果。
6 .序列{10, 18, 4, 3, 6, 12, 1, 9, 18, 8},请给出采用归并排序法 对该序列作升序排序时的每一趟的结果。
7 .采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的算法〃将有序的P[i・.m]和P[m+L・n]归并为有序的Q[i..n]
forfl=m+l, k=i; i<=m &&j<=n; ++k){ 〃将P中的记录由小到大归并到Q 里if (P[i].key <= P[j].key)
Q[k]=P[i++];else Q[k]=P[j++];
)if(i<=m) Q[k..n]=P[i..m]; 〃将剩余的 复制到 Q
if(j〈=n) Q[k..n]=P[j..n]; 〃将剩余的 复制到 Q}// Merge
算法7-9有序表的归并算法递归形式的二路归并排序的算法如下所示。
void MergeSort (ElemType P[ ], ElemType &Q[ ], int sjnt t){〃对具有n个记录的数组P作归并排序，s初值为0, t的初值为n・l
if(s= =t) Q[s]=P[s];
else{
m=(s+t)/2;〃将 平分为 P[s..m] P[m+l..t]
MergeSort(P, Pl, s, m); 〃递归地将归并为有序的 Pl[s..m]
MergeSort(P, Pl, m+l,t); 〃递归地将P[m+L.t]归并为有序的Pl[m+l..t]
Merge(Pl, Q, s, m, t); 〃将 Pl[s..m]和 Pl[m+l..t]归并到 Q[s,.t]
)}// MergeSort
算法7-10二路归并排序的递归算法二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。归并趟数 为(当为奇数时，那么为)。因为每一趟归并就是将两两有序表归并，而每一对有 序表归并时，记录的比拟次数均不大于记录的移动次数(即由一个数组复制到另 一个数组中的记录个数)，而记录的移动次数等于这一对有序表的长度之和，因 此每一趟归并的移动次数均等于数组中记录的个数n,即每一趟归并的时间复杂 度为0(n)。所以，二路归并排序的时间复杂度为O(nlog2n)。
二路归并排序时还需要利用和待排序数组大小相同的一个辅助数组，所以其空间 复杂度为0(n)。
第六节各种内部排序方法的比拟讨论为了在实际应用中更好地选择合适的排序算法，本节对内部排序方法进行的比拟, 主要从以下几个方面综合考虑：时间复杂度、空间复杂度、算法稳定性、算法简 单性、待排序记录数n的大小、记录本身的信息量等。
工、从时间复杂度对内排序的分析1、从时间复杂度对内排序的分析
选择n个整数组成一些随机排序,各种内部排序方法的实际时间如图7-10所示。 从时间复杂度看，所有内部排序方法可以分为两类。插入排序、选择排序和起泡 排序这三种简单排序方法属于第一类，其时间复杂度为0(n2)；堆排序、快速排 序和归并排序这三种排序方法属于第二类，其时间复杂度为O(nlog2n)。这是就 平均情况而言的，如果从最好的情况考虑，那么插入排序和起泡排序的时间复杂度 最好，为。(n),而其他算法的最好情况同平均情况大致相同。如果从最坏的情 况考虑，快速排序的时间复杂度为0(n2),插入排序和起泡排序虽然同平均情况 相同，但系数大约增加一倍，运行速度降低一半，而选择排序、堆排序和归并排 序那么影响不大。
总之，在平均情况下，快速排序最快；在最好情况下，插入排序和起泡排序最快； 在最坏情况下，堆排序和归并排序最快。
2、从空间的复杂度对内排序的分析2、从空间的复杂度对内排序的分析
从空间复杂度看，归并排序属于第一类，其空间复杂度为0(n)；快速排序属于 第二类,其空间复杂度为O(nlog2n)；其它排序方法归为第三类，其空间复杂度 为0(1)。所以，第三类算法的空间复杂度最好，第二类次之，第一类最差。
3、从算法稳定性对内排序的分析3、从算法稳定性对内排序的分析
从算法稳定性看，所有内部排序方法可以分为两类。插入排序、起泡排序和归并 排序属于第一类,是稳定的排序方法;选择排序、快速排序和堆排序属于第二类， 是不稳定的排序方法。相对而言，后者的时间性能较好。
由于大多数情况下排序是按照记录的主关键字进行的，那么所用的排序方法是否稳 定无关紧要。但是如果排序是按照记录的次关键字进行的，那么应根据问题需要慎 重选择排序方法及其描述算法。
4、从算法简单性对内排序的分析4、从算法简单性对内排序的分析
从算法简单性看，一类是简单算法，一般包括插入排序、选择排序和起泡排序, 这些算法都比拟简单和直接，易于理解；另一类是改进后的算法，一般包括堆排 序、快速排序和归并排序，这些算法都比拟复杂。当序列中的记录基本有序或者 n值较小时，直接插入排序是最正确的排序方法，因此常常将它和其他的排序方法 结合使用。
第七节外部排序外部排序是指大文件的排序，待排序的记录存储在外存储器上。本结介绍适合于 外排序方法以及外排序实现过程。
1、外排序的最正确实现方法1、外排序的最正确实现方法
外部排序是指大文件的排序，待排序的记录存储在外存储器上，在排序过程中需 要屡次进行内存和外存之间的交换。对外存文件中的记录进行排序后的结果仍然 被放到原有文件中。
外存磁盘文件能够随机存取任何位置上的信息，所以在数组上采用的各种内部排 序方法都能够用于外部排序。但考虑到要尽量减少访问外存的次数，故归并排序 方法最适合于外部排序。
2、外排序实现过程2、外排序实现过程
外部排序过程可以分成两个相对独立的阶段：
（1）按可用内存的大小，把外存上含有n个记录的文件分成假设干个长度为L的 子文件，把这些子文件依次读入内存，并利用有效的内部排序方法对它们进行排 序，再将排序后得到的有序子文件重新写入外存；
（2）对这些有序子文件逐趟归并，使其逐渐由小到大，直至得到整个有序文件 为止。
其中，第一个阶段即为内部排序的操作，而第二个阶段涉及到了外部排序中的归 并。在前面提到，内存归并排序在开始时是把数组中的每个元素均看作是长度为 1的有序表，在归并过程中，有序表的长度从1开始，依次为2、4、8直至有序表的长度len大于等于待排序的记录数n为止。而在对外存文件的归并 排序中，初始有序表的长度通常是从一个确定的长度开始而不是从1开始，这是 为了能够有效地减少归并的趟数和访问外存的次数，以提高外部排序的效率。所 以，在第一阶段要按照初始有序表确定的长度在原文件上依次建立好每个有序表, 在第二个阶段再调用对文件的归并排序算法完成排序。
第一节概述排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素） 按关键字递增或递减的次序重新排列的过程。本节将解决如下问题：待排序的纪 录如何存储？排序方法有哪些？如何归类？
1、内排序和外排序1、内排序和外排序
排序（Sorting）是数据处理领域一种最常用的运算，它是把一组记录（或元素） 按关键字递增或递减的次序重新排列的过程。
当排序的文件较小，在整个排序过程中，文件涉及的所有数据都可放在内存中， 此时可一次性将文件装入内存进行排序，这就是内部排序。否那么，当被排序的文 件数据量较大，在排序过程中，不能将整个文件涉及的所有数据都同时装入内存, 只能通过屡次内存、外存数据传递、交换，逐步进行排序，这就是外部排序。
2、内排序的归类2、内排序的归类
内排序的方法有很多种，按所用策略不同，常见的有插入排序、交换排序、选择 排序、归并排序；按排序过程中所需的工作量的大小，一般分为简单的排序方法 和改进的排序方法，前者的时间复杂度为0（n2）,后者的时间复杂度为O（nlogn）。 3、排序的一组记录的存储方式3、排序的一组记录的存储方式
待排序的一组记录的存储方式一般有以下三种：（1）顺序存储方式：待排序的 一组记录存放在地址连续的一组存储单元上，相邻的两个记录在存储位置上也是 相邻的；（2）链式存储方式：待排序的一组记录存放在静态链表中（排序时只 改变记录间的次序关系而不做插入、删除操作且在排序结束时仍需调整记录，故 采用静态链表），由指针指示记录之间的次序关系，那么排序过程中仅需修改指针 而不需要移动记录；（3）带有地址向量的顺序存储方式：待排序的一组记录存 储在一组地址连续的存储单元内，同时附设一个地址向量指示各个记录的存储位 置，在排序过程中仅需移动地址向量中这些记录的地址而不需要移动记录本身， 排序结束后按照地址向量中的值调整记录的存储位置。
第二节插入排序
插入排序是所有内排序方法中最简单的排序方法之一，本节将介绍直接插入 排序、改进的插入排序和希尔排序。
1、直接插入排序的算法及评价1、直接插入排序的算法及评价
在内部排序的所有方法中，最简单的排序方法之一是直接插入排序（Straight Insertion Sort） □它是由n・l趟排序组成的。例如,在第i趟排序前（2<i<n）, 位置从1到i-1上的记录是已排过序的，那么第i趟排序是向第1至U i-1个有序记录 之间插入一个新记录，使插入后的记录序列仍为有序，排序过程的每一步类似于 线性表中有序表的插入。
如图7-1显示了一个数组在每一趟插入排序后的情况变化:
初始
(44) 18 74 61 42 31
插入元素
i=2趟排序后
(18 44) 74 61 42 31
18
i=3趟排序后
(18 44 74) 61 42 31
74
i=4趟排序后
(18 44 61 74) 42 31
61
i=5趟排序后
(18 42 44 61 74) 31
42
i=6趟排序后
(18 31 42 44 61 74)
31
图7.1插入排序例如
如图7-1所示，当i=3趟排序后，即第4趟排序前，第1个位置到第3个位 置的记录都是有序的，准备将第4个记录61插入。插入后，即i=4时的有序序 歹U： (18, 44, 61, 74) o
一般情况下，对于第i趟排序前，记录l~i-l是已排过序的，需要将第i个记 录插入其中，使之仍为有序。插入中，首先通过比拟插入记录和已排序记录的大 小找到插入的位置，然后将所在位置的记录及其后记录依次后移一个位置。其具 体算法如下：
void InsertSort(ElemType P[ ], int n){〃对具有n个记录的数组P作直接插入排序
//n个记录存放在数组中，P[0]留作''哨兵"使用for(i=2; i<=n; i++)
if(P[i].key<P[I-l].KEY){span v>将 P[i]插入有序子表P[0]=P[i]；
P[i]=P[i-l]；forQ=i-2;P[0].key<P[J].KEY; span j-)<>
P[j+l]=p[j];〃向后移动数组记录P[j+l]=P[O];〃插入记录
) }//InsertSort算法7-1直接插入排序
从处理过程来看，该算法简洁、易实现，下面我们对该算法的效率进行分析。
从空间上看，它只需要一个位置作为辅助空间，算法中为P[0]；从时间上看, 该算法的主要操作和影响算法效率的步骤为比拟两个记录的关键字大小和移动 记录。当待排序的记录按关键字有序排列(本算法中有序为非递减排列)时，所 需的关键字间的比拟次数到达最小值(即n・l),不需要移动记录；反之，当待 排序记录按关键字非递增排列(相对本算法为反序)时，那么比拟次数到达最大值 (即(n+2)(n-l)/2),记录移动次数也到达最大值(即(n+4)(n-l)/2)。对于随 机排列的记录序列，比拟次数和移动记录的次数约为~/4。所以，插入排序的时 间复杂度为0(己)。该算法在n较小时或待排序的记录基本有序时还是较为适用 的。
2、折半插入排序的算法及评价2、折半插入排序的算法及评价
折半插入排序(Binary Insertion Sort)是一种改进的插入排序方法。
由插入记录的基本操作可知，每次操作都是向有序表中插入记录，在查找插入位 置时，我们可以通过'折半查找〃来减少记录关键字的比拟次数。具体算法如下:
void BiInsertSort(ElemType P[ ], int n){ 〃对具有n个记录的数组P作折半插入排序//n个记录存放在数组P[l「n]中 for(i=2; i<=n; i++){
P[0]=P[i];〃P[0]作为辅助空间〃折半查找插入位置
〃折半位置

〃折半查找插入位置
〃折半位置
low=l; high=i-l; while(low<=high){ m=(low+high)/2;if(P[O].key<P[M].KEY) span < high=Mm-l;、在低半区插入 else low=m+l;〃在高半区插入
}//whilefor(j=i-l; j>=high+l; j") P[j+l]=P[j]; 〃向后移动数组记录
P[high+l]=P[0];〃插入记录)
}//BiInsertSort算法7-2折半插入排序
和普通插入排序相比拟，折半插入排序的辅助空间也为一个位置；在时间上，虽 然平均移动记录的次数不变，但是关键字的比拟次数减少。本算法的时间复杂度 仍为0(n2)。
3、希尔排序的思想及优点3、希尔排序的思想及优点
希尔排序使用一个序列hl, h2,…,ht,叫做增量序列(Increment Sequence)。 在使用增量hk的一趟排序之后，对于每一个记录i有P[i]WP[i+hk],即所有相隔 hk的记录都被排序。此时称该序列是hk-排序(hk-sorted)的。而且，希尔排 序具有一个很重要的性质，一个hk-排序后的序列，将在以后的排序中一直保持 它的hk-排序性。假如不是这样，那么该算法就不具有什么意义了，因为前面各 趟排序的结构就不会被后面各趟排序给打乱。如图7-2为一个序列在各趟排序后 的情况。
希尔排序的优点是综合了直接插入排序的优点：在文件长度n较小时或文件基本 有序的情况下，直接插入排序还是具有较高效率的。希尔排序通过使用增量hk 进行分组，同一组中的元素进行比拟并排序，这样在前面几趟排序时，每组长度 较小，可使发生逆序的元素较快地向前大幅度调整，而在后面几趟排序时，尽管 此时每组长度已经较大，但每组内的数据基本有序，需要调整的数据已经很少了， 这样从整体上实现了效率的提高。
4、希尔排序算法及评价4、希尔排序算法及评价
hk-排序的一般做法是，对于hk,hk+l,…，n中的每一个位置i,其中的记录在序 列i,i-hk,i-2hk…中处于正确的位置，使该序列有序，即对该序列进行插入排序。 如图7-2中所示，对于5-排序中的81, 35,41进行插入排序，使之成为35,41, 81 的有序序列。具体算法如下：
void ShellSort(日emType P[ ], int n){〃对具有n个记录的数组P作希尔排序
//n个记录存放在数组中，P[0]留作''哨兵〃使用for(increment=n/2; increment>0; increment/=2)
〃该增量序列为Shell建议序列，使用简单，但效率不高for(i=increment+l; i<=n; i++)〃针对某一增量进行一趟希尔排序
if(P[i].key<P[I-INCREMENT] .key){P[0]=P[i]；
for0=i-increment; j>0 && P[0] .key <P[J] j-="increment)<o:pH .key;>P[j+increment]=P|j];
P[j+increment]=P[O];}//if
}//ShellSort算法7-3希尔排序
在希尔排序中，我们可采用不同的增量序列进行排序，而对于不同的增量序列, 其算法的时间复杂度是不同的。对于Shell建议序列，即hk为1,2,4,8,n/2, 算法的时间复杂度为0(n2)；对于Hibbard增量序列，即hk=2k-l,算法的时间 复杂度为。(n3/2)；对于 Sedgewick 增量序列，即 hk=9*4k-9*2k+l 或 4k-3* 2k + 1,算法的时间复杂度为O(n7/6)第三节交换排序
交换排序是指待排序纪录间通过比拟和''交换〃而进行的排序。本节着重介绍冒泡 排序和快速排序。
工、冒泡排序的基本思想1、冒泡排序的基本思想
在需要通过大量''交换''进行的排序中，最简单的一种就是我们所熟知的起泡排序 (Bubble Sort) □它的基本思路是：比拟相邻的两个数，只要发生逆序，就进行交换，以便将小的调到前头。具体例如见图7-3。
起泡排序的过程如图7-3所示：第一趟的第一次将7和8交换，第二次将8和4 交换，……，如此共进行5次，得到7-4-3-1-0-8的顺序，可以看到：关键字为 最大的8的记录已''沉底〃，成为最下面的一个记录，而关键字小的记录''上浮〃。 关键字为最小的。的记录已'浮起〃一个位置。经过第一趟排序，已经得到关键字 最大的记录。然后进行第二趟排序，对剩余的记录的关键字7-4-3T-0进行比拟， 同7-3(a)类似，经过4次比拟得到关键字为次大的7的记录。如此类推，对于6 个记录要进行5趟排序，才能使6个记录按关键字大小顺序排列。在第一趟排序 中，记录关键字的两两比拟需要进行5次，第二趟进行4次……第五趟进行1次。 在此过程中，关键字较小的记录好比水中的气泡逐趟向上漂浮，而关键字较大的 记录好比石块往下沉，每一趟有一块''最大'’的石头沉到水底。
如果有n个数，那么要进行n-1趟排序。在第一趟排序中，要进行n-1次比拟，在 第i趟排序中，已有i-1个数据元素已排好序，只需在第1个至第n-i+1个元素 中进行排序，那么要进行n-i次比拟。当然，可以设置标识信息记录每趟是否有逆 序发生，假设发现某趟无逆序发生，那么整个排序结束。
通过上述分析可以看出，对于最好的情况，即\'正序〃序列，那么只需进行一趟排序， 排序过程中，进行n-1次关键字的比拟，且不移动记录；对于最坏的情况，即''逆 序''序列，那么需进行n-1趟排序，需进行(即n(n-l)/2)次比拟，并做同数量级 的记录的移动。所以，起泡法的时间复杂度为0(n2)。
2、快速排序的原理2、快速排序的原理
快速排序(Quicksort)是于1962年提出的一种平均性能最好的分 类方法，它的平均运行时间是0(n log n)。该算法之所以性能好，主要是由于非 常精炼和高度优化的内部循环。
它的基本思想是，按一定的规那么选择某个控制记录作为枢轴(Pivot),首先通 过交换各个记录间的位置将它放置在它应该在的位置，使它之前的记录的关键字 都比它的关键字小，它之后的记录的关键字都比它的关键字大。对它前后的记录 各自形成的子序列，再按同样的规那么处理，直到所有记录都被安置在相应的位置 上。
3、快速排序算法及评价3、快速排序算法及评价
快速排序的具体算法如下：
Status QuickSort(ElemType P[ ], int start, int end){〃对数组P从start到end的记录进行快速排序
i=start; j=end;if (i>=j) return 0;〃该序列仅剩一个记录
m=(i+j)/2;〃取该序列中间位置的记录while(i<J){
〃当i<Jv span》时，检索记录while(P[i].key<=P[m] .key && i<=j) i++;
while(P[j] .key >=P[m] .key &&j>=i) j--;if(i<J) span P[i]<>^—>P[j];
){P[j]-->P[m]; m=j;}
〃如果j在m的位置或在它右边，那么枢轴记录应该在位置j,否那么在位置i处else {P[i卜—>P[m]; m=i;}
QuickSort(P[ ], start, m-1);〃对枢轴左边的元素进行排序QuickSort(P[ ], m+1, end); 〃对枢轴右边的元素进行排序 return OK;
}// Quicksort算法7-4快速排序
在快速排序中，记录移动次数通常小于记录比拟次数，因为只有当记录出现逆序 (即 P[i].key>P[m].key 和 P[j].key<P[M].KEY< span>)时才需要把 P〈]同 P[j] 交换，即移动记录。因此，讨论快速排序的时间复杂度只要按它的比拟次数讨论 即可。下面我们来分析快速排序的平均时间性能。
假设T(n)为对n个记录P[0.・n-l]进行排序平均所需的时间，那么由算法可见，T(n)=cn+T(m-l)+T(n-m)(c 为某个常数)
由于是求平均性能，假设待排序的序列包括子序列是随机排列的，那么上式中，m 取1至n之间的任一值概率是相同的，快速排序所需的时间的平均值那么为 T(n)=cn+
=cn+假定T(l)wb (b为某个常数)，那么可推出
T(n)=
<
<(n>2)所以，快速排序的时间复杂度为0(n In n)。另外，在取枢轴时，还有其他的改 进方法，如P[start], P[end], P[(start+end)/2]三者取关键字中等大小的一个记 录进行比拟。这种改进可进一步提高快速排序的平均性能，具体算法请由读者思 考写出。
第四节选择排序选择排序是使用得排序方法之一，主要包括简单项选择择排序和堆排序。
1、简单项选择择排序的基本思想1、简单项选择择排序的基本思想
简单项选择择排序(Simple Selection Sort)是一种简单的排序方法。它每次从待排 序的记录序列中(范围从i到n)选择出关键字最小的记录，把该记录与序列中 的第i个记录交换位置。
对于中的记录序列进行简单项选择择排序的过程为：第一趟排序时，待排序 记录包含P[l]~P[n],经过选择和交换后，P[l]为关键字最小的记录；第二趟排 序时，待排序记录包含P[2]~P[n],经过选择和交换后，P[2]为仅次于P[l]的关 键字最小的记录；依次类推，经过n-1趟排序，P[l]~P[n]就成为了有序表，整 个简单项选择择排序过程结束。
2、堆的含义2、堆的含义
堆是一个序列，其中每个记录包含一个关键字，序列中的位置k处的关键字，至 少大于位置2k和2k+l处(假设这些位置存在于序列中)的关键字。
在这种结构中，对近似于一个公司团体，其中每个雇员(除了堆的最底层)恰好 管理两个其他雇员。
3、堆排序的实现步骤3、堆排序的实现步骤
排序的过程分为两个步骤。首先，必须重新组合列表中的记录项，使它们满足堆 的要求。第二，重复移去堆的顶层，并提升另一个记录项顶替他的位置。
对于第二步我们需要进一步解释，当堆顶记录被移去后，堆顶出现空缺，通过对 序列中剩余的n・l个记录进行整理，可设想为完成如上所述的公司内部 职位调整，那么可使符合堆的性质，并将原堆顶记录放置到位置P[n]。 然后，再按照上述步骤对进行操作。
4、堆的建立算法及调整算法4、堆的建立算法及调整算法
根据堆的实现步骤描述，我们可得出该算法主体局部如下：
void HeapSort(ElemType P[ ], int n){〃对具有n个记录的数组P作堆排序
BuildHeap(P, n);〃对序列进行调整，使之成为堆序列for(i= n; i>=2; i-){
temp=P[i];〃暂存序列尾部元素P[i]=P[l]；〃将堆顶元素放置到序列尾部
InsertHeap(temp, 1, i-1, P );〃对序列进行整理使为堆序列)
}//HeapSort算法7-6堆排序 在继续编写函数BuildHeap和InsertrtHeap前，我们先看一下列图7-6所示的堆排 序的开始的几个步骤。如图7-7所示：
在第一步中，将最大关键字96从列表的第一个记录移动到最后一个记录，最初 在最后一个位置的记录39,被放置到临时变量temp中。为了找出重新组合堆和 插入39的方式，观察根结点的两个子结点88、73,它们的关键字均比其它结点 的大，因此，这两个结点中关键字大的记录可提升为根结点，即88。然后，我 们再在根结点被移去的子树中重复这个过程，那么54被插入到88原来的位置。 下一步中，将比拟原54的两个子结点，但是他们不存在，因此树中记录提升的 过程停止，temp=39被插入到54原来所处的位置中。
然后我们重复这一算法，直到树中只剩一个结点为止。过程如图7-8所示： 根据上述过程，可得出InsertHeap如下：
void InsertHeap(ElemType temp, int root, int end, ElemType P[ ]){ 〃对序列进行整理，使之成为堆序列，然后插入temp child=2*root;〃取左孩子结点while(child<=end){
if(child< P[child]<P[child+l]) &&>假设右孩子结点关键字更大child++;
if(temp>=P[child])break;
else{P[root]=P[child];〃提升孩子结点
root=child;
child=2*root;
〃准备整理子树
P[root]=temp;〃重新插入结点
}// InsertHeap算法7・7堆的调整算法
下面，我们剩余的任务就是开始构建初始的堆。首先，一棵仅有一个结点的二叉 树必符合堆的特性，因此，不用担忧树的任何叶子结点，即序列中后半局部的任 何记录。如果从序列的中心位置开始，从后向前处理，可以使用InsertHeap函 数将每个记录插入到由后面所有记录所组成的局部堆中，从而构建完整的堆。函 数如下：
void BuildHeap(日emType P[ ], int n){〃将具有n个记录的数组P整理为堆
for(i=n/2; i>=l; i--)InsertHeap(P[i], i, n, P);
)算法7-8建立初始堆的算法
在运算次数最大的情况下，InsertHeap函数中比拟的次数至多为2 log(end/root), 赋值的次数至多是log(end/root)。使111=口/2,即在BuildHe叩函数中，对 InsertHeap函数进行了 m次调用，因为i的值的范围从m到1。所以比拟的总 次数大约是类似的，在排序过程中，比拟次数为：
所以，在运算次数最大的情况下，总的比拟次数是2nlogn+O(n),赋值次数为 nlogn+0(n)o第五节归并排序
把两个或多个有序表合并成一个有序表的过程称为归并。归并排序的最大特点在 于这种排序方法的稳定性，本节主要介绍二路归并。
工、二路归并排序的实现过程1、二路归并排序的实现过程
对有序表反复利用归并过程进行排序的方法称为归并排序(Merging Sort)。利 用二路归并操作的排序称为二路归并排序。
二路归并排序的过程是：
(1)把无序表中的每一个元素都看作是一个有序表，那么有n个有序子表；
(2)把n个有序子表按相邻位置分成假设干对(假设n为奇数，那么最后一个子表单 独作为一组)，每对中的两个子表进行归并，归并后子表数减少一半；
(3)反复进行这一过程，直到归并为一个有序表为止。
2、二路归并排序的实现算法2、二路归并排序的实现算法
二路归并排序过程的核心操作是将一维数组中相邻的两个有序表归并为一个有 序表，其算法如下所示。
void Merge(ElemType P[ ], ElemType & Q[ ], int i, int m, int n){