数据基础结构 10

教案纸（首页）第1页第次课学时授课时间_______教学主题排序的定义和相关概念；插入排序算法；教学要求1、掌握排序的定义和相关概念。2、掌握插入排序算法，包括直接插入排序、折半插入排序和希尔排序。教学重点直接插入排序、折半插入排序和希尔排序教学难点接插入排序、折半插入排序和希尔排序教学方法讲授教学手段多媒体、板书讲授要点1、排序的定义和排序的相关概念。2、直接插入排序算法及其性能分析。3、折半插入排序算法及其性能分析。4、希尔排序算法及其性能分析。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记什么是"排序"？简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。例如，将下列记录序列

{52,49,80,36,14,58,61,23,97,75}

调整为序列

{14,23,36,49,52,58,61,75,80,97}

一般情况下，对排序的定义为：

假设含有n个记录的序列为：

{r1,r2,…,rn}(10-1)

它们的关键字相应为

{k1,k2,…,kn}

对式（10-1）的记录序列进行排序就是要确定序号1，2，…，n的一种排列

p1,p2,…,pn，

使其相应的关键字满足如下的非递减（或非递增）的关系：

(10-2)

也就是使式(10-1)的记录序列重新排列成一个按关键字有序的序列

(10-3)

当待排序记录中的关键字ki(i=1,2,…,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是唯一的；反之，若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。假设ki=kj(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中ri领先于rj(即i<j)。若在排序后的序列中ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。在某些有特殊要求的应用问题中需要考虑所用排序方法的稳定性的问题。

根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：（1）内部排序：在排序进行的过程中不使用计算机外部存储器的排序过程。2）外部排序：在排序进行的过程中需要对外存进行访问的排序过程。本章仅讨论各种内部排序的方法。

内部排序的过程是一个逐步扩大记录的"有序序列"区域的长度的过程。大多数排序方法在排序过程中将出现如动画所示"有序"和"无序"两个区域，其中有序区内的记录已按关键字非递减有序排列，而无序区内为待排记录，通常称"使有序区中记录数目增加一个或几个"的操作过程为"一趟排序"。按何种策略扩大有序区域将导致不同的排序方法。例如在无序区域中选取一个关键字最小记录加到有序区域中的排序方法称为"选择类"的排序法，除此之外还有插入类、交换类、归并类和计数类等排序方法。本章仅就各类介绍一二个典型算法。

待排序的记录序列可以用顺序表表示，也可以用链表表示。直接插入排序

插入排序的准则是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。一趟直接插入排序的基本思想则是:在对记录序列R[1..n]的排序过程中，区段R[1..i-1]中的记录已按关键字非递减的顺序排列，将R[i]插入到有序序列R[1..i-1]中，使区段R[1..i]中的记录按关键字非递减顺序排列，如右图所示。

由此实现一趟插入排序的步骤为：

1)在R[1..i-1]中查找R[i]的插入位置，即确定j(0≤j＜i＝使得

R[1..j].key≤R[i].key＜R[j+1..i-1].key

2＝将R[j+1..i-1]中的记录后移一个位置；

3＝将R[i]插入到j+1的位置。

和9.2.2中讨论的顺序查找类似，为了避免在查找过程中判别循环变量是否出界，设置R[0]为监视哨，并在查找的同时进行"记录后移"，如动画演示所示。

算法10.1

voidInsertPass(SqList&L,inti)

{

//已知L.r[1..i-1]中的记录已按关键字非递减的顺序有序排列,本算法实

//现将L.r[i]插入其中,并保持L.r[1..i]中记录按关键字非递减顺序有序

L.r[0]=L.r[i];//复制为哨兵

for(j=i-1;L.r[0].key<L.r[j].key;--j)

L.r[j+1]=L.r[j];//记录后移

L.r[j+1]=L.r[0];//插入到正确位置

}//InsertPass

显然，只含一个记录的序列是有序的，因此令i从2起，逐个插入直到n便可实现整个插入排序，算法如下。

算法10.2

voidInsertSort(SqList&L)

{

//对顺序表L作直接插入排序

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-1].key){//将L.r[i]插入有序子表

L.r[0]=L.r[i];L.r[i]=L.r[i-1];

for(j=i-2;L.r[0].key<L.r[j].key;--j)

L.r[j+1]=L.r[j];//记录后移

L.r[j+1]=L.r[0];//插入到正确位置

}//if

}//InsertSortR[1..n]表示记录序列的长度为n，1..n表示它们的序号(下标)连续地从1至n。

如果L.r[i].key≥L.r[i-1].key，则L.r[1..r]已经有序，不需要再进行查找和插入；反之，若已知L.r[i].key＜L.r[i-1].key，查找插入位置可从i-2开始。直接插入排序的时间复杂度从上述排序过程可见，排序中的两个基本操作是：（关键字间的）比较和（记录的）移动。因此排序的时间性能取决于排序过程中这两个操作的次数。从直接插入排序的算法可见，这两个操作的次数取决于待排记录序列的状态，当待排记录处于"正序"(即记录按关键字从小到大的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于"逆序"(即记录按关键字从大到小的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最多，如下表所列。待排记录序列状态"比较"次数"移动"次数正序n-10逆序

若待排记录序列处于随机状态，则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度。一般情况下，直接插入排序的时间复杂度为O(n2)。"移动记录"的次数包括监视哨的设置。

先分析一趟直接插入排序的情况：

若L.r[i].key≥L.r[i-1].key，只进行"1"次比较，不移动记录；

若L.r[i].key＜L.r[1].key，需进行"i"次比较，i+1次移动。

整个插入排序的过程中，i从2至n，则得

折半插入排序

由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用"折半查找"查询插入位置，由此得到的插入排序算法为"折半插入排序"。算法如下：

算法10.3

voidBInsertSort(SqList&L)

{

//对顺序表L作折半插入排序

for(i=2;i<=L.length;++i)

{

L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]

low=1;high=i-1;

while(low<=high)

{//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;//折半

if(L.r[0].key<L.r[m].key)}high=m-1;//插入点在低半区

elselow=m+1;//插入点在高半区

}//while

for(j=i-1;j>=low;--j)L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];//插入

}

}//BInsertSort

但是，折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O(n2)。表插入排序

表插入排序是以静态链表作待排记录序列的存储结构实现的插入排序。这个静态链表由存储记录的顺序表和附加的指针数组构成，静态链表中的指针实际上指的是数组的下标。

表插入排序分两步进行：首先构造一个有序链表；然后按照"附加指针"的指示将结点中的记录重新排列成一个有序序列。

先看一个具体的例子。

从例子中可见，构成有序链表的过程和前面讨论的直接插入排序的过程基本相同，先生成一个只含一个记录的有序链表，之后将从第2个至最后一个记录逐个插入，差别仅在于查找插入位置是从前到后进行查询直至找到一个记录的关键字大于当前待插入的记录的关键字，因此在查询过程中应该保持一个指"前驱"结点的指针。其算法在此不再详述，请读者自行补充。

所谓"重排记录"是将记录移动到正确位置（即按关键字从小至大有序排列）。在重排的过程中设置了三个指针：其中i指示当前需要"归位"的记录的正确位置；p指示该记录的原始位置；q指示第i+1个记录（即指针p所指记录的后继）的原始位置。显然，重排的主要操作是互换p和i所指记录，以便使第i小关键字记录归位至正确位置，但由于互换记录破坏了链表的链接关系，可利用和当前已归位记录相应的指针予以修补，由于i值从小至大变化，因此第i个记录当前所在的原始位置p必定大于i，若当前p的值比i小，说明该位置的记录已被移走，可由相应指针值找到它当前所在位置。算法如下：

算法10.4

voidArrange(SqList&L，intNext[])

{

//根据Next[]中的指针值调整记录位置，使得L中记录

//按关键字非递减有序顺序排列

p=Next[0];//p指示第一个记录的当前位置

for(i=1;i<L.length-1;++i)

{//SL.r[1..i-1]中记录已按关键字有序排列，

//第i个记录在L中的当前位置应不小于i

while(p<i)p=Next[p];//找到第i个记录，并用p指示其在L中当前位置

q=Next[p];//q指示尚未调整的后继记录

if(p!=i){

L.r[p]←→L.r[i];//交换记录，使第i个记录到位

Next[i]=p;//指向被移走的记录，使得以后可由while循环找回

}//if

p=q;//p指向下一个将要调整的记录

}//for

}//Arrange

容易看出，在重排过程中至多进行3(n-1)次移动记录，然而整个表插入排序过程也仅仅是减少了移动记录的时间，所以它的时间复杂度仍为O(n2)。希尔排序

希尔排序又称"缩小增量排序"，它的基本思想是，先对待排序列进行"宏观调整"，待序列中的记录"基本有序"时再进行直接插入排序。

先看一个具体例子的希尔排序的过程。例如一个含11个关键字的序列(16，25，12，30，47，11，23，36，9，18，31)，先对它进行"增量为5"的插入排序，即分别使(R1,R6,R11)、(R2,R7)、(R3,R8)、(R4,R9)和(R5,R10)为有序序列，然后将增量"缩小到3"，排序结果使(R1,R4,R7,R10)、(R2,R5,R8,R11)和(R3,R6,R9)分别成为有序序列，此时序列中在关键字18，23，25，31和47之前的关键字均比它们小，即在进行最后一趟排序时这几个关键字都不需要"往前进行"插入，之后经过最后一趟插入排序即得到有序序列。

从上述例子的排序过程可见，由于希尔排序在前几趟的排序过程中，关键字较大的记录是"跳跃式"地往后移动，从而使得在进行最后一趟插入排序之前序列中记录的关键字已基本有序，只需作少量关键字比较和移动记录，由此减少了整个排序过程中所需进行的"比较"和"移动"的次数。所谓"基本有序"是指，在序列中的各个关键字之前，只存在少量关键字比它大的记录。算法10.5

voidShellInsert(SqList&L，intdk)

{

//对顺序表L作一趟增量为dk的希尔排序

for(i=dk+1;i<=L.length;++i)

if(L.r[i].key<L.r[i-dk].key){//将L.r[i]插入有序子表

L.r[0]=L.r[i];L.r[i]=L.r[i-dk];

for(j=i-2*dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)

L.r[j+dk]=L.r[j];//记录后移

L.r[j+dk]=L.r[0];//插入到正确位置

}//if

}//ShellInsert

算法10.6

voidShellSort(SqList&L,intdlta[],intt)

{

//按增量序列dlta[0..t-1]对顺序表L作希尔排序

for(k=0;k<t;++t)

ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序

}//ShellSort

希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为2t-k-1(k=0,1,…，t-1)时，希尔排序的时间复杂度为O(n3/2)。希尔排序的增量序列dlta[]可以有多种取法，但必须是，

(1)dlta[]中各值没有除1之外的公因子；

(2)dlta[t-1]必须为1。

例如，dlta[]=……,9,5,3,2,1

或dlta[]=……,31,15,7,3,1

或dlta[]=……,40,13,4,1等。

第次课学时授课时间______教学主题交换排序算法；选择排序算法教学要求1、掌握交换排序算法，包括冒泡排序和快速排序。2、掌握选择排序算法，包括简单选择排序和堆排序。教学重点冒泡排序算法、快速排序算法、堆排序算法教学难点冒泡排序算法、快速排序算法、堆排序算法教学方法讲授教学手段多媒体、板书讲授要点1、冒泡排序算法及其性能分析。2、快速排序算法及其性能分析。3、简单选择排序算法及其性能分析。4、堆定义及特点、堆排序算法及其性能分析。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记交换排序法(快速排序)起泡排序

起泡排序是交换类排序方法中的一种简单排序方法。其基本思想为：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。如右图所示，在第i趟起泡排序之前，区段R[n-i+2..n]中的记录已按关键字从小到大有序排列，而区段R[1..n-i+1]中的记录不一定有序，但该区段中所有记录的关键字均不大于有序序列中记录的关键字(即小于或等于R[n-i+2].key)，则第i趟起泡排序的操作为，从第1个记录起，逐个和相邻记录的关键字进行比较，若第j(1≤j≤n-i)个记录的关键字大于第j+1个记录的关键字，则互换记录，由此可将区段R[1..n-i+1]中关键字最大的记录"交换"到R[n-i+1]的位置上，从而使有序序列的长度增1。显然，如果第i趟起泡排序的过程中，没有进行任何记录的交换，则表明区段R[1..n-i+1]中的记录已经按关键字从小到大有序排列，由此不再需要进行下一趟的起泡，即起泡排序已经完成，可见排序结束的条件是(i=n-1)或者（第i趟的起泡中没有进行记录交换），如算法10.7所示。

算法10.7

voidBubbleSort(SqList&L)

{

//对顺序表L作起泡排序

for(i=L.length,change=TRUE;i>1&&change;--i){

change=FALSE;

for(j=1;j<i;++j)

if(L.r[j].key>L.r[j+1].key)

{L.r[j]←→L.r[j+1];change=TRUE}

}//fori

}//BubbleSort

分析起泡排序的时间复杂度：和直接插入相似，排序过程中所进行的"比较"和"移动"操作的次数取决于待排记录序列的状态，在待排记录处于"正序"时取最小值，此时只需进行一趟起泡排序，反之，在待排记录处于"逆序"时取最大值，此时需进行n-1趟起泡，列表如下：待排记录状态"比较"次数"移动"次数正序n-10逆序算法中设立了一个标志一趟起泡中是否进行了交换记录操作的布尔型变量change，在每一趟起泡之前均将它设为"FALSE"，一旦进行记录交换，则将它改为"TRUE"，因此change=TRUE是进行下一趟起泡的必要条件。当待排序列中的记录已按关键字有序排列时，显然，在进行n-1次关键字的比较，而不需要交换记录；然而，当待排序列中的记录按关键字逆序排列时，需进行n-1趟起泡，并且每一趟起泡都需进行所有记录的互换，因此进行的关键字比较的总数为：

，

进行的记录移动的总数为：

。在算法10.7中，经过每一趟起泡，待排记录序列的上界i都只是减1。但实际上，有的时候起泡的上界可以缩减不止1个记录的位置，例如右侧所示例子。

从这个例子可见，在一趟起泡的过程中，有可能只是在区段的前端进行记录的交换，而其后端记录已经按关键字有序排列，由此应在算法中设置一个指示"最后一个进行交换的记录的位置"的变量。改进后的起泡算法如下：

算法10.8

voidBubbleSort(SqList&L)

{

//对顺序表L作起泡排序

i=L.length;

while(i>1){//i>1表明上一趟曾进行过记录的交换

lastExchangeIndex=1;

for(j=1;j<i;j++){

if(L.r[j+1].key<L.r[j].key){

L.r[j]←→.r[j+1]；//互换记录

lastExchangeIndex=j;//记下进行交换的记录的位置

}//if

}//for

i=lastExchangeIndex;

//一趟起泡后仍处于无序状态的最后一个记录的位置

}//while

}//BubbleSort

快速排序

起泡排序是通过一趟"起泡"选定关键字最大的记录，所有剩余关键字均小于它的记录继续进行排序，快速排序则是通过一趟排序选定一个关键字介于"中间"的记录，从而使剩余记录可以分成两个子序列分别继续排序，通常称该记录为"枢轴"。如右图所示，假设一趟快速排序之后枢轴记录的位置为i，则得到的无序记录子序列(1)R[s..i-1]中记录的关键字均小于枢轴记录的关键字，反之，得到的无序记录子序列(2)R[i+1..t]中记录的关键字均大于枢轴记录的关键字，由此这两个子序列可分别独立进行快速排序。

例如，关键字序列(52,49,80,36,14,75,58,97,23,61)

经第1趟快速排序之后为(23,49,14,36)52(75,58,97,80,61)

经第2趟快速排序之后为(14)23(49,36)52(61,58)75(80,97)

经第3趟快速排序之后为(14,23,36,49,52,58,61,75,80,97)

快速排序的算法如下：

算法10.9

voidQSort(RcdTypeR[],ints,intt)

{

//对记录序列R[s..t]进行快速排序

if(s<t){//长度大于1

pivotloc=Partition(R,s,t);

//对R[s..t]进行一趟快排，并返回枢轴位置

QSort(R,s,pivotloc-1);//对低子序列递归进行排序

QSort(R,pivotloc+1,t);//对高子序列递归进行排序

}//if

}//Qsort

算法10.10

voidQuickSort(SqList&L)

{

//对顺序表L进行快速排序

QSort(L.r,1,L.length);

}//QuickSort

快速排序的算法是一个递归函数，因此算法10.9中必须引入一对参数s和t作为待排序区域的上下界。在算法的递归调用过程执行中，这两个参数随着"区域的划分"而不断变化。对顺序表L进行快速排序调用算法10.9时，s和t的初值应分别置为1和L.length。一趟快排也称"一次划分"，即将待排序列R[s..t]"划分"为两个子序列R[s..i-1]和R[i+1..t]，i为一次划分之后的枢轴位置。可以取待排序列中任何一个记录作为枢轴，但为方便起见，通常取序列中第一个记录R[s]为枢轴，以它的关键字作为划分的依据。划分可如下进行：设置两个指针low和high，分别指向待排序列的低端s和高端t。若R[high].key<R[s].key，则将它移动至枢轴记录之前；反之，若R[low].key>R[s].key，则将它移动至枢轴记录之后，并为避免枢轴来回移动，可先将枢轴R[s]暂存在数组的闲置分量R[0]中。如右侧所示为"一次划分"过程的一个例子。一次划分（一趟快速排序）的算法如下：

算法10.11

intPartition(RcdTypeR[],intlow,inthigh)

{

//对记录子序列R[low..high]进行一趟快速排序，并返回枢轴记录

//所在位置，使得在它之前的记录的关键字均不大于它的关键字，

//而在它之后的记录的关键字均不小于它的关键字

R[0]=R[low];//将枢轴记录移至数组的闲置分量

pivotkey=R[low].key;//枢轴记录关键字

while(low<high){//从表的两端交替地向中间扫描

while(low<high&&R[high].key>=pivotkey)

--high;

R[low++]=R[high];//将比枢轴记录小的记录移到低端

while(low<high&&R[low].key<=pivotkey)

++low;

R[high--]=R[low];//将比枢轴记录大的记录移到高端

}//while

R[low]=R[0];//枢轴记录移到正确位置

returnlow;//返回枢轴位置

}//Partition

可以推证，快速排序的平均时间复杂度为O(nlogn)，在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法，如果借用起泡排序中设置记录"交换与否"的布尔变量的作法，快速排序也适用于已经有序的记录序列。选择排序法简单选择排序

选择排序的基本思想是，在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。第i(i=1,2,…,n-1)趟的简单选择排序（序列中前i-1个记录的关键字均小于后n-i+1个记录的关键字）的作法是，在后n-i+1个记录中选出关键字最小的记录，并将它和第i个记录进行互换。如右图所示。

算法10.12

voidSelectSort(SqList&L)

{

//对顺序表L作简单选择排序

for(i=1;i<L.length;++i){//选择第i小的记录，并交换到位

j=i;

for(k=i+1;k<=L.length;k++)

//在L.r[i..L.length]中选择关键字最小的记录

if(L.r[k].key<L.r[j].key)j=k;

if(i!=j)L.r[j]←→L.r[i];//与第i个记录互换

}//for

}//SelectSort

无论待排序列处于什么状态，选择排序所需进行的"比较"次数都相同，为，而"移动"次数在待排序列为"正序"时达最小为0，在"逆序"时达最大为3(n-1)。堆排序

何谓"堆"？

若含n个元素的序列{K1,K2,…,Kn}满足下列关系则称作"小顶堆"或"大顶堆"。"堆顶"元素为序列中的"最小值"或"最大值"。

例如，{12,39,20,65,47,34,98,81,73,56}为"小顶堆"；

{98,81,34,73,56,12,20,39,65,47}为"大顶堆"。

若将上述数列视作为一个完全二叉树，则堆顶元素即为二叉树的根结点，和分别为ki的"左子树根"和"右子树根"，如右图所示。

利用堆的特性进行的排序方法即为"堆排序"，其排序过程如下：

假设待排关键字序列为：{34,39,20,65,47,12,98,73,81,56}

1）先将它调整为大顶堆：{98,81,34,73,56,12,20,39,65,47}

2）互换"堆顶"和待排序列中

的最后的关键字：{47,81,34,73,56,12,20,39,65,98}

3）在待排序列中舍去最大关键字，将其余部

分重新调整为堆：{81,73,34,65,56,12,20,39,47}98

4）重复2）和3）直至待排序列中只剩一个关键字为止。

可见，堆排序的两个关键问题是：

1）如何将一个无序序列调整为堆？

2）如何在互换堆顶之后重新调整为堆？"堆排序"也是一种选择类的排序方法，每一趟从记录的无序序列中选出一个关键字最大或最小的记录，和简单选择所不同的是，在第一趟选最大或最小关键字记录时先"建堆"，从而减少之后选择次大或次小关键字等一系列记录时所需的比较和移动次数。

如上所述，已知关键字序列{98,81,34,73,56,12,20,39,65,47}是大顶堆，当将"98"和"47"互换之后，它就不再是个堆。但此时"98"已是选出的最大关键字，不需要再参加排序，由此只要对其余关键字进行排序，如果能将它重新调整为一个大顶堆，这就等于选出了第二个最大关键字。而此时的关键字序列有下列特点：如图二叉树所示，除"根结点"之外，其"左子树"和"右子树"都仍然是堆。由此只要"从上到下"进行"筛选"可将该序列重新调整为大顶堆。

首先将"47"移至暂存空间R[0]，将"81"和"34"进行比较后得到的"大者"与"47"进行比较，由于81>47，则应将"81"移至根结点的位置，之后将"73"和"56"进行比较后得到的"大者"与"47"进行比较，同样因为73>47，将"73"上移，同理需将"65"移至它的双亲位置，而将"47"移至它原来的位置(因为此时已达叶子结点，无孩子结点可比较)。由此得到一个新的大顶堆，选出第2个最大关键字"81"，之后类似地在互换"81"和"47"之后，进行从上到下的筛选可选出第3个最大关键字"73"，依次类推直至只剩下一个关键字为止。从上到下的"筛选"算法如下所示：

算法10.13

voidHeapAdjust(SqList&H,ints,intm)

{

//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，

//本函数依据关键字的大小对H.r[s]进行调整，使H.r[s..m]成为一

//个大顶堆（对其中记录的关键字而言）

H.r[0]=H.r[s];//暂存根结点的记录

for(j=2*s;j<=m;j*=2){//沿关键字较大的孩子结点向下筛选

if(j<m&&H.r[j].key<H.r[j+1].key)

++j;//j为关键字较大的孩子记录的下标

if(H.r[0].key>=H.r[j].key)break;//不需要调整，跳出循环

H.r[s]=H.r[j];s=j;//将大关键字记录往上调

}//for

H.r[s]=H.r[0];//回移筛选下来的记录

}//HeapAdjust

如何"建堆"？

建堆的过程是一个"从下到上"调整堆的过程。显然，叶子结点是个堆，对记录无序系列中"最后一个"分支结点而言，满足筛选的前提，即除根结点之外，其左、右子树都是堆，由此可调用算法10.13将它调整为一个堆。类似地，"从后往前"看每个记录都满足筛选的前提，依次进行调整直至对以第1个记录为根的"二叉树"进行筛选之后，整个记录序列就是一个大顶堆了。例如右侧动画所示为对前述记录无序序列进行建堆的过程。

算法10.14

voidHeapSort(SqList&H)

{

//对顺序表H进行堆排序

for(i=H.length/2;i>0;--i)//将H.r[1..H.length]建成大顶堆

HeapAdjust(H,i,H.length);

H.r[1]←→H.r[H.length];//互换"堆顶"和"堆底"的记录

for(i=H.length-1;i>1;--i){

HeapAdjust(H,1,i);//从根开始调整，将H.r[1..i]重新调整为大顶堆

H.r[1]←→H.r[i];

//互换"堆顶"和当前的"堆底"，使已有序的记录沉积在底部

}//for

}//HeapSort

可以证明，堆排序的时间复杂度为O(nlogn)。和选择排序雷同，无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好"或"最坏"的状态。第次课学时授课时间________教学主题归并排序算法；基数排序算法；各种内排序方法性能分析和应用教学要求1、掌握归并排序算法，包括二路归并排序。2、掌握基数排序算法，包括最低位优先和最高位优先排序。3、掌握各种内排序方法的性能分析和比较。教学重点归并排序算法；基数排序算法；各种内排序方法性能分析和应用教学难点二路归并算法；基数排序算法；各种内排序方法性能分析和应用教学方法讲授、练习教学手段多媒体、板书、上机实操讲授要点1、归并排序的特点和过程。2、二路归并排序算法及其性能分析。3、基数排序的特点和过程。4、基数排序算法及其性能分析。5、各种内排序方法性能分析和应用。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）教学内容备注与后记2-路归并排序

归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过"逐趟归并"使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。

2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列"归并"为一个有序序列，如右侧所示。这个操作对顺序表而言是极其容易实现的，只要依关键字从小到大进行"复制"即可，如下算法所示。

算法10.15

voidMerge(RcdTypeSR[],RcdTypeTR[],inti,intm,intn)

{

//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]

for(j=m+1,k=i;i<=m&&j<=n;++k)

{//将SR中记录按关键字从小到大地复制到TR中

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];

}

while(i<=m)TR[k++]=SR[i++];//将剩余的SR[i..m]复制到TR

while(j<=n)TR[k++]=SR[j++];//将剩余的SR[j..n]复制到TR

}//Merge

容易看出，2-路归并排序的时间复杂度为O(nlogn)。基数排序多关键字的排序

一般情况下，对多关键字排序的定义为：

假设含有n个记录的序列为：

(R1,R2….,Rn)

每个记录Ri中含有d个关键字，则称该记录序列对关键字有序是指：对于序列中任意两个记录Ri和Rj（1≤i<j≤n）都满足下列有序关系：

其中K0被称作最主位关键字，Kd-1被称作最次位关键字。

通常实现多关键字排序可以有两种策略：一是最主位优先（MSD法），另一是最次位优先（LSD法）。

最主位优先的作法是：先对最主位关键字K0进行排序，得到若干子序列，其中每个子序列中的记录都含相同的K0值，之后分别就每个子序列对关键字K1进行排序，致使K1值相同的记录构成长度更短的子序列，依次重复，直至就当前得到的各个子序列对Kd-2进行排序之后得到的每个子序列中都具有相同的关键字，分别对这些子序列按Kd-1从小到大进行排序，最后由这些子序列依次相连所得序列便是排序的最后结果，即对关键字有序。最次位优先的作法是，在继续对"前一位"排序时不需要将当前所得对其后一位有序的序列分割成若干子序列进行，而是整个序列依次对Kd-1、对Kd-2直至对K0进行排序即可.基数排序的两种实现方法

实现基数排序可以有两种不同算法。

一、链式基数排序

类似于表插入排序，附设指针数组将顺序表视作一个"静态链表"，利用"修改指针"实现分配和收集。同时设置rd个队列的头指针和尾指针，分别指示各队列的"头结点"和"尾结点"在链表中的位置。

首先初始化空队列，即将每个队列的头指针front[i]和尾指针rear[i]均设为"0"；"分配"时将记录"插入"队列，若队列为空，则仅需修改队列的头、尾指针，令它们指向该插入记录，否则在修改队列的尾指针的同时尚需修改当前队尾记录的指针；"收集"时依次头尾相接地链接各非空队列所指记录，即改变各非空队列尾指针所指记录的指针，令它们指向"下一"非空队列头指针所指记录，最后一个非空队列尾指针所指记录的指针应为"空"。

在描述基数排序的算法之前，尚需重新定义记录和顺序表类型：

constMAX_NUM_OF_KEY=8;

//关键字项数的最大值，暂定为8

constRADIX=10;

//关键字基数，此为十进制整数的基数

typedefstruct{

KeysTypekeys[MAX_NUM_OF_KEY];//关键字

InfoTypeotheritems;//其它数据项

}RcdType;//基数排序中的记录类型

typedefstruct{

RcdTyper[MAXSIZE+1];

intlength;//顺序表长度

intbitsnum;//关键字位数

}SqList;//顺序表类型

分析链式基数排序的时间复杂度：假设n为记录个数，rd为基数值，d为构成逻辑关键字的关键字位数。由于每一趟的"分配"都是对全部记录处理一遍，因此它的时间复杂度是O(n)，而每一趟的"收集"只是巡查一遍队列，依次将各非空队列的队尾指针所指结点链接到下一个非空队列的队头指针所指结点，因此它的时间复杂度是O(rd)，因此一趟分配和收集的时间复杂度为O(n+rd)，对每一位关键字进行一趟分配和收集，因此总的时间复杂度为O(d(n+rd))，一般情况下，相比n而言，rd要小得多，因此可简写为O(dn)。换句话说，当待排序序列中的记录数量很大，而逻辑关键字的"位数"较小，此时用基数排序法进行排序将比快速排序的效率更高。二、利用"计数"和"复制"的方法实现的基数排序算法

由于在排序的过程中利用了"计数"策略，故在此称它为"计数基数排序"，其算法如下所示。

算法10.21

voidRadixSort(SqList&L)

{

//对顺序表L进行基数排序

RcdTypeC[L.length+1];//开设同等大小的辅助空间用于复制数据

i=bitsnum-1;

while(i>=0){

RadixPass(L.r,C,L.length,i);

//对L.r进行一趟基数排序，排序结果存入C

i--;

if(i>=0){

RadixPass(C,L.r,L.length,i);

//对C进行一趟基数排序，排序结果存入L.r

i--;

}//if

else

for(j=1;j<=L.l