排序概念市公开课一等奖省赛课获奖课件

第9章排序排序概念第1页9.1排序概念排序概念第2页排序（sort）或分类

所谓排序，就是要整理文件中统计，使之按关键字递增(或递减)次序排列起来。其确切定义以下：

输入：n个统计R1，R2，…，Rn，其对应关键字分别为K1，K2，…，Kn。

输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

排序概念第3页2．排序运算依据--关键字

用来作排序运算依据关键字，能够是数字类型，也能够是字符类型。

关键字选取应依据问题要求而定。

【例】在高考成绩统计中将每个考生作为一个统计。每条统计包含准考证号、姓名、各科分数和总分数等项内容。若要惟一地标识一个考生统计，则必须用"准考证号"作为关键字。若要按照考生总分数排名次，则需用"总分数"作为关键字。

排序概念第4页排序稳定性当待排序统计关键字均不相同时，排序结果是惟一，不然排序结果不唯一。

在待排序文件中，若存在多个关键字相同统计，经过排序后这些含有相同关键字统计之间相对次序保持不变，该排序方法是稳定；若含有相同关键字统计之间相对次序发生改变，则称这种排序方法是不稳定。

排序概念第5页01姓名9802850376049805100排序概念第6页注意：排序算法稳定性是针对全部输入实例而言。即在全部可能输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定。

排序概念第7页排序方法分类1．按是否包括数据内、外存交换分

在排序过程中，若整个文件都是放在内存中处理，排序时不包括数据内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据内、外存交换，则称之为外部排序。

注意：

①内排序适合用于统计个数不很多小文件

②外排序则适合用于统计个数太多，不能一次将其全部统计放人内存大文件。

排序概念第8页内1内2内3内4内5外1外2排序概念第9页2．按策略划分内部排序方法能够分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。排序概念第10页按性能分类简单排序算法：性能o(n2)复杂排序算法：性能o(nlog2n)排序概念第11页排序算法分析1．排序算法基本操作

大多数排序算法都有两个基本操作：

(1)比较两个关键字大小；

(2)改变指向统计指针或移动统计本身。

注意：

temp=a[i];a[i]=a[i+1];a[i+1]=tem

第(2)种基本操作实现依赖于待排序统计存放方式。

排序概念第12页2．待排文件惯用存放方式（1）以次序表(或直接用向量)作为存放结构

排序过程：对统计本身进行物理重排（即经过关键字之间比较判定，将统计移到适当位置）

（2）以链表作为存放结构

排序过程：无须移动统计，仅需修改指针。通常将这类排序称为链表(或链式)排序；

（3）用次序方式存放待排序统计，但同时建立一个辅助表(如包含关键字和指向统计位置指针组成索引表)

排序过程：只需对辅助表表目进行物理重排（即只移动辅助表表目，而不移动统计本身）。适合用于难于在链表上实现，仍需防止排序过程中移动统计排序方法。排序概念第13页用索引表实现排序b[0]b[1]4078212502836345948955628673774538501965a[10]b[10]排序概念第14页3．排序算法性能评价（1）评价排序算法好坏标准

评价排序算法好坏标准主要有两条：

①执行时间和所需辅助空间

②算法本身复杂程度

（2）排序算法空间复杂度

若排序算法所需辅助空间并不依赖于问题规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。

非就地排序普通要求辅助空间为O(n)。

（3）排序算法时间开销

大多数排序算法时间开销主要是关键字之间比较和统计移动。有排序算法其执行时间不但依赖于问题规模，还取决于输入实例中数据状态。排序概念第15页文件次序存放结构表示#definenl00//假设文件长度，即待排序统计数目typedefStudinfoInfoType;

typedefintKeyType；//假设关键字类型

typedefstruct{//统计类型

KeyTypekey；//关键字项

InfoTypeotherinfo；//其它数据项，类型InfoType依赖于详细应用而定义

}RecType；

typedefRecTypeSeqList[n+1]；//SeqList为次序表类型，表中第0个单元普通用作哨兵排序概念第16页9.2插入法排序插入排序(InsertionSort)基本思想是：每次将一个待排序统计，按其关键字大小插入到前面已经排好序数组中适当位置，直到全部统计插入完成为止。

本节介绍两种插入排序方法：直接插入排序和希尔排序。排序概念第17页直接插入排序基本思想1、基本思想

假设待排序统计存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前有序区R[1..i-1]中，生成含n个统计有序区。

排序概念第18页排序概念第19页012345672623547421103923265474211039i=2i=7jjjji3551217排序概念第20页for(i=2;i<=n;i++){在1到i-1之间找到一个适当位置把a[i]插入到这个适当位置}排序概念第21页2、第i-1趟直接插入排序：

通常将一个统计R[i](i=2，3，…，n-1)插入到当前有序区，使得插入后仍确保该区间里统计是按关键字有序操作称第i-1趟直接插入排序。

排序过程某一中间时刻，R被划分成两个子区间R[1．．i-1]（已排好序有序区）和R[i．．n]（当前未排序部分，可称无序区）。

直接插入排序基本操作是将当前无序区第1个统计R[i]插人到有序区R[1．．i-1]中适当位置上，使R[1．．i]变为新有序区。因为这种方法每次使有序区增加1个统计，通常称增量法。

排序概念第22页2．改进方法一个查找比较操作和统计移动操作交替地进行方法。

详细做法：

将待插入统计R[i]关键字从右向左依次与有序区中统计R[j](j=i-1，i-2，…，1)关键字进行比较：

①若R[j]关键字大于R[i]关键字，则将R[j]后移一个位置；

②若R[j]关键字小于或等于R[i]关键字，则查找过程结束，j+1即为R[i]插入位置。

关键字比R[i]关键字大统计均已后移，所以j+1位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。排序概念第23页直接插入排序算法1．算法描述

voidlnsertSort(SeqListR)

{//对次序表R中统计R[1..n]按递增序进行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中全部keys，则R[i]

//应在原有位置上

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]副本

do{//从右向左在有序区R[1．．i-1]中查找R[i]插入位置

R[j+1]=R[j]；//将关键字大于R[i].key统计后移

j--；

}while(R[0].key<R[j].key)；//当R[i].key≥R[j].key时终止

R[j+1]=R[0]；13//R[i]插入到正确位置上

}//endif

}//InsertSort排序概念第24页直接插入排序算法1．算法描述

voidlnsertSort(SeqListR)

{//对次序表R中统计R[1..n]按递增序进行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中全部keys，则R[i]

//应在原有位置上

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]副本

do{//从右向左在有序区R[1．．i-1]中查找R[i]插入位置

R[j+1]=R[j]；//将关键字大于R[i].key统计后移

j--；

}while(R[0].key<R[j].key)；//当R[i].key≥R[j].key时终止

R[j+1]=R[0]；13//R[i]插入到正确位置上

}//endif

}//InsertSort排序概念第25页直接插入排序算法1．算法描述main()voidlnsertSort(SeqListR)

{

inti，j；

for(i=1+d;i<=n；i++)

if(R[i].key<R[i-d].key){

R[0]=R[i];j=i-d;

do{

R[j+d]=R[j]；

j=j-d；

}while(j>0&&R[0].key<R[j].key)；

R[j+d]=R[0]；

}

}排序概念第26页voidf1(inta[2]){a[0]=23;a[1]=100;}main(){intb[2]={18,10};f1(b);pritnf(}排序概念第27页2．哨兵作用

算法中引进附加统计R[0]称监视哨或哨兵(Sentinel)。

哨兵有两个作用：

①进人查找(插入位置)循环之前，它保留了R[i]副本，使不致于因统计后移而丢失R[i]内容；

②它主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而防止了在该循环内每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

注意：

①实际上，一切为简化边界条件而引入附加结点(元素)均可称为哨兵。

【例】单链表中头结点实际上是一个哨兵

②引入哨兵后使得测试查找循环条件时间大约降低了二分之一，所以对于统计数较大文件节约时间就相当可观。对于类似于排序这么使用频率非常高算法，要尽可能地降低其运行时间。所以不能把上述算法中哨兵视为雕虫小技，而应该深刻了解并掌握这种技巧排序概念第28页排序过程示例次数R[0]R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]初始710132025304255排序概念第29页算法性能分析最坏情形排序概念第30页排序概念第31页最好情形(原来已经排序好）Cmin=n-1=O(n)Mmin=0=O(1)平均情况C=O(n2)M=O(直接插入法排序最大特点，当原来已经排序好(基本上已经排序好），则速度最快，当原来序列大致已排序好时，也比较快。排序概念第32页注意：

初始文件按关键字递增有序，简称"正序"。

初始文件按关键字递减有序，简称"反序"。

排序概念第33页9.2.2希尔排序(ShellSort)

希尔排序(ShellSort)是插入排序一个。因D．L．Shell于1959年提出而得名。

希尔排序基本思想

基本思想：

先取一个小于n整数d1作为第一个增量，把文件全部统计分成d1个组。全部距离为dl倍数统计放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述分组和排序，直至所取增量dt=1(dt<dt-l<…<d2<d1)，即全部统计放在同一组中进行直接插入排序为止。

该方法实质上是一个分组插入方法。

给定实例shell排序排序过程

假设待排序文件有10个统计，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

增量序列取值依次为：

5，3，1排序概念第34页Shell排序算法实现1．不设监视哨算法描述

voidShellPass(SeqListR，intd)

{//希尔排序中一趟排序，d为当前增量

for(i=d+1;i<=n；i++)//将R[d+1．．n]分别插入各组当前有序区

if(R[i].key<R[i-d].key){

R[0]=R[i];j=i-d；//R[0]只是暂存单元，不是哨兵

do{//查找R[i]插入位置

R[j+d]=R[j]；//后移统计

j=j-d；//查找前一统计

}while(j>0&&R[0].key<R[j].key)；

R[j+d]=R[0]；//插入R[i]到正确位置上

}//endif

}//ShellPass

void

ShellSort(SeqListR){intincrement=n；//增量初值，不妨设n>0

do{

increment=increment/3+1；//求下一增量

ShellPass(R，increment)；//一趟增量为incrementShell插入排序

}while(increment>1)

}//ShellSort排序概念第35页

分析排序概念第36页次数R[0]R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]初始4938659776132749550413132749550449386597768132749550449386597765311304493827495565977604232738494955657697排序概念第37页shell排序算法性能分析时间复杂度为=O(nlog2n)<O(n2)算法不稳定排序概念第38页2．算法空间复杂度分析

算法所需辅助空间是一个监视哨，辅助空间复杂度S(n)=O(1)。是一个就地排序。

3．直接插入排序稳定性

直接插入排序是稳定排序方法。排序概念第39页8.3交换排序交换排序基本思想是：两两比较待排序统计关键字，发觉两个统计次序相反时即进行交换，直到没有反序统计为止。

应用交换排序基本思想主要排序方法有：冒泡排序和快速排序。

排序概念第40页8.3.1冒泡排序1、排序方法

将被排序统计数组R[1..n]垂直排列，每个统计R[i]看作是重量为R[i].key气泡。依据轻气泡不能在重气泡之下标准，从下往上扫描数组R：凡扫描到违反本标准轻气泡，就使其向上"飘浮"。如此重复进行，直到最终任何两个气泡都是轻者在上，重者在下为止。

排序概念第41页（2）第一趟扫描从无序区底部向上依次比较相邻两个气泡重量，若发觉轻者在下、重者在上，则交换二者位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]内容。

第一趟扫描完成时，"最轻"气泡就飘浮到该区间顶部，即关键字最小统计被放在最高位置R[1]上。

排序概念第42页（3）第二趟扫描扫描R[2..n]。扫描完成时，"次轻"气泡飘浮到R[2]位置上……

最终，经过n-1

趟扫描可得到有序区R[1..n]

排序概念第43页规律n个数n-1趟第1趟比较n-1次第2趟比较n-2次第i趟比较n-i第n-1趟比较1次for(i=1;i<=n-1;i++)for(j=0;j<n-i;j++)if(a[j]>a[j+1]){a[j]与a[j+1]交换;}排序概念第44页排序示例趟14938383838384949494965656527272727276549494949496514233241排序概念第45页排序示例1513131517172525343487545497979787排序概念第46页（2）详细算法voidBubbleSort(SeqListR){//R（l..n)是待排序文件，采取自下向上扫描，对R做冒泡排序

inti，j；

Booleanexchange；//交换标志

for(i=1;i<n;i++){//最多做n-1趟排序

exchange=FALSE；//本趟排序开始前，交换标志应为假

for(j=n-1;j>i；j--)//对当前无序区R[i..n]自下向上扫描

if(R[j+1].key<R[j].key){//交换统计

temp=R[j+1]；//R[0]不是哨兵，仅做暂存单元

R[j+1]=R[j]；

R[j]=temp；

exchange=TRUE；//发生了交换，故将交换标志置为真

}

if(exchange==FALSE)//本趟排序未发生交换，提前终止算法

return；

}//endfor(外循环)

}//BubbleSort排序概念第47页4、算法分析（1）算法最好时间复杂度

若文件初始状态是正序，一趟扫描即可完成排序。所需关键字比较次数C和统计移动次数M均到达最小值：

Cmin=n-1

Mmin=0。

冒泡排序最好时间复杂度为O(n)。

排序概念第48页（2）算法最坏时间复杂度

若初始文件是反序，需要进行n-1趟排序。每趟排序要进行n-i次关键字比较(1≤i≤n-1)，且每次比较都必须移动统计三次来到达交换统计位置。在这种情况下，比较和移动次数均到达最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序最坏时间复杂度为O(n2)。

排序概念第49页（2）算法最坏时间复杂度若初始文件是反序，需要进行n-1趟排序。每趟排序要进行n-i次关键字比较(1≤i≤n-1)，且每次比较都必须移动统计三次来到达交换统计位置。在这种情况下，比较和移动次数均到达最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序最坏时间复杂度为O(n2)。

排序概念第50页（3）算法平均时间复杂度为O(n2)

即使冒泡排序不一定要进行n-1趟，但因为它统计移动次数较多，故平均时间性能比直接插入排序要差得多。

排序概念第51页（4）算法稳定性

冒泡排序是就地排序，且它是稳定。

排序概念第52页(1)记住最终一次交换发生位置lastExchange冒泡排序

在每趟扫描中，记住最终一次交换发生位置lastExchange，（该位置之前相邻统计均已经有序）。下一趟排序开始时，R[1..lastExchange-1]是有序区，R[lastExchange..n]是无序区。这么，一趟排序可能使当前有序区扩充多个统计，从而降低排序趟数。详细算法【参见习题】。

(2)改变扫描方向冒泡排序

①冒泡排序不对称性

能一趟扫描完成排序情况：

只有最轻气泡位于R[n]位置，其余气泡均已排好序，那么也只需一趟扫描就能够完成排序。

【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。

需要n-1趟扫描完成排序情况：

当只有最重气泡位于R[1]位置，其余气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。

排序概念第53页9.3.2快速排序(QuickSort)1、算法思想

快速排序是C.R.A.Hoare于1962年提出一个划分交换排序。它采取了一个分治策略，通常称其为分治法(Divide-and-ConquerMethod)。

（1）分治法基本思想

分治法基本思想是：将原问题分解为若干个规模更小但结构与原问题相同子问题。递归地解这些子问题，然后将这些子问题解组合为原问题解。排序概念第54页（2）快速排序基本思想

设当前待排序无序区为R[low..high]，利用分治法可将快速排序基本思想描述为：

①分解：

在R[low..high]中任选一个统计作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中全部统计关键字均小于等于基准统计(不妨记为pivot)关键字pivot.key，右边子区间中全部统计关键字均大于等于pivot.key，而基准统计pivot则位于正确位置(pivotpos)上，它无须参加后续排序。排序概念第55页②求解：

经过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③组合：

因为当"求解"步骤中两个递归调用结束时，其左、右两个子区间已经有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

排序概念第56页2、快速排序算法QuickSort

voidQuickSort(SeqListR，intlow，inthigh)

{//对R[low..high]快速排序

intpivotpos；//划分后基准统计位置

if(low<high){//仅当区间长度大于1时才须排序

pivotpos=Partition(R，low，high)；//对R[low..high]做划分

QuickSort(R，low，pivotpos-1)；//对左区间递归排序

QuickSort(R，pivotpos+1，high)；//对右区间递归排序

}

}//QuickSort

排序概念第57页3、划分算法Partition（1）简单划分方法

①详细做法

第一步：(初始化)设置两个指针i和j，它们初值分别为区间下界和上界，即i=low，i=high；选取无序区第一个统计R[i](即R[low])作为基准统计，并将它保留在变量pivot中；

第二步：令j自high起向左扫描，直到找到第1个关键字小于pivot.key统计R[j]，将R[j])移至i所指位置上，这相当于R[j]和基准R[i](即pivot)进行了交换，使关键字小于基准关键字pivot.key统计移到了基准左边，交换后R[j]中相当于是pivot；然后，令i指针自i+1位置开始向右扫描，直至找到第1个关键字大于pivot.key统计R[i]，将R[i]移到i所指位置上，这相当于交换了R[i]和基准R[j]，使关键字大于基准关键字统计移到了基准右边，交换后R[i]中又相当于存放了pivot；接着令指针j自位置j-1开始向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准pivot最终位置，将pivot放在此位置上就完成了一次划排序概念第58页③划分算法：intPartition(SeqListR，inti，intj){ReceTypepivot=R[i]；while(i<j){

while(i<j&&R[j].key>=pivot.key)

j--；

if(i<j)

R[i++]=R[j]；

while(i<j&&R[i].key<=pivot.key)

i++；

if(i<j)

R[j--]=R[i];

}//endwhile

R[i]=pivot；

returni；

}//partition排序概念第59页③划分算法：intPartition(SeqListR，inti，intj){//调用Partition(R，low，high)时，对R[low..high]做划分，//并返回基准统计位置

ReceTypepivot=R[i]；//用区间第1个统计作为基准‘while(i<j){//从区间两端交替向中间扫描，直至i=j为止

while(i<j&&R[j].key>=pivot.key)//pivot相当于在位置i上

j--；//从右向左扫描，查找第1个关键字小于pivot.key统计R[j]

if(i<j)//表示找到R[j]关键字<pivot.key

R[i++]=R[j]；//相当于交换R[i]和R[j]，交换后i指针加1

while(i<j&&R[i].key<=pivot.key)//pivot相当于在位置j上

i++；//从左向右扫描，查找第1个关键字大于pivot.key统计R[i]

if(i<j)//表示找到了R[i]，使R[i].key>pivot.key

R[j--]=R[i];//相当于交换R[i]和R[j]，交换后j指针减1

}//endwhile

R[i]=pivot；//基准统计已被最终定位

returni；

}//partition排序概念第60页4、快速排序执行过程排序概念第61页快速递归过程排序概念第62页6、算法分析快速排序时间主要花费在划分操作上，对长度为k区间进行划分，共需k-1次关键字比较。排序概念第63页（1）最坏时间复杂度

最坏情况是每次划分选取基准都是当前无序区中关键字最小(或最大)统计，划分结果是基准左边子区间为空(或右边子区间为空)，而划分所得另一个非空子区间中统计数目，仅仅比划分前无序区中统计个数降低一个。

所以，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需比较次数为n-i(1≤i≤n-1)，故总比较次数到达最大值：

Cmax=n(n-1)/2=O(n2)

假如按上面给出划分算法，每次取当前无序区第1个统计为基准，那么当文件统计已按递增序(或递减序)排列时，每次划分所取基准就是当前无序区中关键字最小(或最大)统计，则快速排序所需比较次数反而最多。

排序概念第64页（2）最好时间复杂度在最好情况下，每次划分所取基准都是当前无序区"中值"统计，划分结果是基准左、右两个无序子区间长度大致相等。总关键字比较次数：

0(nlgn)

排序概念第65页9.4选择法排序选择排序(SelectionSort)基本思想是：每一趟从待排序统计中选出关键字最小统计，次序放在已排好序子文件最终，直到全部统计排序完成。

惯用选择排序方法有直接选择排序和堆排序。

排序概念第66页直接选择排序(StraightSelectionSort)1、直接选择排序基本思想

n个统计文件直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小统计R[k]，将它与无序区第1个统计R[1]交换，使R[1..1]和R[2..n]分别变为统计个数增加1个新有序区和统计个数降低1个新无序区。……

排序概念第67页③第i趟排序第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小统计R[k]，将它与无序区第1个统计R[i]交换，使R[1..i]和R[i+1..n]分别变为统计个数增加1个新有序区和统计个数降低1个新无序区。

这么，n个统计文件直接选择排序可经过n-1趟直接选择排序得到有序结果。排序概念第68页直接选择法排序初始4938659776132749第1趟1338659776492749排序概念第69页3、算法描述voidSelectSort(SeqListR){

inti，j，k；

for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)

k=i；

for(j=i+1;j<=n;j++)//在当前无序区R[i..n]中选key最小统计R[k]

if(R[j].key<R[k].key)

k=j;//k记下当前找到最小关键字所在位置

if(k!=i){//交换R[i]和R[k]

R[0]=R[i]；R[i]=R[k]；R[k]=R[0]；//R[0]作暂存单元

}//endif

}//endfor

}//SeleetSort排序概念第70页4、算法分析（1）关键字比较次数

不论文件初始状态怎样，在第i趟排序中选出最小关键字统计，需做n-i次比较，所以，总比较次数为：

n(n-1)/2=0(n2)

（2）统计移动次数

当初始文件为正序时，移动次数为0

文件初态为反序时，每趟排序均要执行交换操作，总移动次数取最大值3(n-1)。

直接选择排序平均时间复杂度为O(n2)。

（3）直接选择排序是一个就地排序排序概念第71页（4）稳定性分析

直接选择排序是不稳定排序概念第72页9.4.2堆排序排序概念第73页1、堆排序定义n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足以下性质(简称为堆性质)：

(1)ki≤K2i且ki≤K2i+1

或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)

若将此序列所存放向量R[1..n]看做是一棵完全二叉树存放结构，则堆实质上是满足以下性质完全二叉树：树中任一非叶结点关键字均小于(或大于)其左右孩子(若存在)结点关键字。

排序概念第74页例【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应完全二叉树分别如小根堆示例和大根堆示例所表示。

排序概念第75页示例排序概念第76页2、大根堆和小根堆根结点(亦称为堆顶)关键字是堆里全部结点关键字中最小者堆称为小根堆。

根结点(亦称为堆顶)关键字是堆里全部结点关键字中最大者，称为大根堆。

注意：

①堆中任一子树亦是堆。

②以上讨论堆实际上是二叉堆(BinaryHeap)，类似地可定义k叉堆排序概念第77页34，25，72，62，17，53，32,753262327522494917low=425large=8排序概念第78页3、堆排序特点

堆排序(HeapSort)是一树形选择排序。

堆排序特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树次序存放结构，利用完全二叉树中双亲结点和孩子结点之间内在关系【参见二叉树次序存放结构】，在当前无序区中选择关键字最大(或最小)统计。

排序概念第79页5、堆排序

堆排序利用了大根堆(或小根堆)堆顶统计关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字统计变得简单。排序概念第80页（1）用大根堆排序基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始无序区

②再将关键字最大统计R[1](即堆顶)和无序区最终一个统计R[n]交换，由此得到新无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

③因为交换后新根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大统计R[1]和该区间最终一个统计R[n-1]交换，由此得到新无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，一样要将R[1..n-2]调整为堆。

……

直到无序区只有一个元素为止。

排序概念第81页（2）大根堆排序算法基本操作：①初始化操作：将R[1..n]结构为初始堆；

②每一趟排序基本操作：将当前无序区堆顶统计R[1]和该区间最终一个统计交换，然后将新无序区调整为堆(亦称重建堆)。排序概念第82页（3）堆排序算法：

voidHeapSort(SeqListR)

{//对R[1..n]进行堆排序，不妨用R[0]做暂存单元

inti；

BuildHeap(R)；//将R[1-n]建成初始堆

for(i=n;i>1；i--){//对当前无序区R[1..i]进行堆排序，共做n-1趟。

R[0]=R[1]；R[1]=R[i];R[i]=R[0]；//将堆顶和堆中最终一个统计交换

Heapify(R，1，i-1)；//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质

}//endfor

}//HeapSort排序概念第83页筛选法调整堆voidHeapify(SeqListR,intlow,inthigh){intlarge;RecTypetemp=R[low];//temp=25for(large=2*low;large<=high;large*=2）//large=16{if(large<high&&R[large].key<R[Large+1].key)large++;if(temp.key>=R[large].key)//25>=75break;R[low]=R[large];low=large;low=8}R[low]=temp;}排序概念第84页建堆算法voidbuildHeap(SeqListR){inti;

for(i=n/2;i>0;i--)Heapify(R,i,n);//对R进行调整，从i这个元素开始，到n}排序概念第85页建堆过程示例(初始)13172324429116051388422324160591排序概念第86页建堆过程示例(2)

88与23交换后42138824912316054213918824160523排序概念第87页建堆过程示例(3)

i=3符合要求,不调整42138824912316054213912324160523排序概念第88页建堆过程示例(4)

i=213与88调整42881324912316054288912324160513排序概念第89页建堆过程示例(5)

i=113与88调整05882324421316059188422324160513排序概念第90页调整过程O(nlog2n)O(n2)排序概念第91页初始状态91884924491342059188422324160513排序概念第92页调整(1)13882324429116059188422324160513排序概念第93页调整(1A)88132324429116059188422324160513排序概念第94页调整(1B)88242313429116059188422324160513排序概念第95页效率或时间复杂度O(nlog2n)8个队，按循环赛，要进行多少场比赛。8排序概念第96页9.5归并排序两路归并算法

1、算法基本思绪

设两个有序子文件(相当于输入堆)放在同一向量中相邻位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

排序概念第97页（1）合并过程

合并过程中，设置i，j和p三个指针，其初值分别指向这三个统计区起始位置。合并时依次比较R[i]和R[j]关键字，取关键字较小统计复制到R1[p]中，然后将被复制统计指针i或j加1，以及指向复制位置指针p加1。

重复这一过程直至两个输入子文件有一个已全部复制完成(不妨称其为空)，此时将另一非空子文件中剩下统计依次复制到R1中即可。排序概念第98页归并示例504025198352318123ijkp排序概念第99页o(nlog2n),存放空间O(n),O(1)3253133364427863325423lowmhigh排序概念第100页n个数归并示例231235425187101960234287191235511060428735512319121060排序概念第101页2、归并算法

voidMerge(SeqListR，intlow，intm，inthigh)

{//将两个有序子文件R[low..m)和R[m+1..high]归并成一个有序

//子文件R[low..high]

inti=low