数据结构教程（Java语言描述）（第2版 微课视频版） 课件 第10章 排序

第10章

排序10.1排序的基本概念10.2插入排序CONTENTS提纲10.3交换排序10.5归并排序10.4选择排序10.6基数排序10.7各种内排序方法的比较和选择10.8外排序1/7010.1排序的基本概念1.什么是排序

所谓排序，就是要整理表中的元素，使之按关键字递增或递减有序排列，本章仅讨论递增排序的情况，在默认情况下所有的排序均指递增排序。排序的输入输出如下：输入：n个元素序列为R0、R1、…、Rn-1，其相应的关键字分别为k0、k1、…、kn-1。输出：Ri0，Ri1，…，Rin-1

，使得ki0≤ki1≤…≤kin-1。2/70在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序。反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。2.内排序和外排序3/70内排序3.内排序的分类基于比较的排序不基于比较的排序插入排序交换排序选择排序归并排序基数排序4/704.基于比较的排序算法的性能基于比较的排序算法中，主要进行以下两种基本操作：比较：元素关键字之间的比较。移动：元素从一个位置移动到另一个位置。5/70排序算法的性能由算法的时间和空间确定的，而时间又是由比较和移动的次数确定的。若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素为正序。反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表中元素为反序。6/70是否基于比较的排序算法的下界(R3,R1,R2)(R3,R2,R1)(R2,R3,R1)(R2,R1,R3)(R1,R3,R2)是否(R1,R2,R3)k1≤k2k2≤k3①k1≤k3②③是否是否k1≤k3④k2≤k3⑤⑥是否(R1,R2,R3)(R1,R2,R3)(R1,R3,R2)(R2,R1,R3)(R2,R3,R1)n=3的决策树正序不变，逆序交换！3!=6个叶子结点7/708/70基于比较排序算法的平均时间复杂度不可能优于O(nlog2n)n个元素排序结果有n!种情况，对应的决策树是一棵有n!个叶子结点的二叉树。设其高度为h，其中没有单分支结点，总结点个数=2n!-1，其高度等同于含2n!-1个结点的完全二叉树的高度，则h=

log2(2n!)

=log2n!+1，而log2n!≤nlog2n-1.45n，即h的下界为nlog2n。排序中移动次数与比较次数属于同数量级。n个元素采用基于比较的排序方法最坏情况下的时间下界为nlog2n。5.排序的稳定性当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排序的结果不一定唯一。如果待排序的表中，存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。9/70

以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。假设关键字为int类型。待排序的顺序表中元素类型如下：classRecType

//顺序表元素类型{intkey; //存放关键字，假设关键字为int类型Stringdata; //存放其他数据，假设为String类型publicRecType(intd)//构造方法{key=d;}}6.排序数据的组织10/70顺序表查找类SqListSortClass（除基数排序外）publicclassSqListSortClass{

//顺序表排序类finalintMAXN=100; //表示最多元素个数RecType[]R; //存放排序的元素intn; //实际元素个数publicvoidswap(inti,intj)} //交换R[i]和R[j]RecTypetmp=R[i];R[i]=R[j];R[j]=tmp;}publicvoidCreateR(int[]a){ //由关键字序列a构造顺序表R[0..n-1]R=newRecType[MAXN];for(inti=0;i<a.length;i++)R[i]=newRecType(a[i]);n=a.length;}publicvoidDisp(){ //输出顺序表R[0..n-1]for(inti=0;i<n;i++)System.out.print(R[i].key+"");System.out.println();}11/70publicvoidCreateR1(int[]a){ //由a构造R[1..n]，用于堆排序R=newRecType[MAXN];for(inti=0;i<a.length;i++)R[i+1]=newRecType(a[i]);n=a.length;}publicvoidDisp1(){ //输出顺序表R[1..n]

，用于堆排序for(inti=1;i<=n;i++)System.out.print(R[i].key+"");System.out.println();}

//各种基于比较的排序方法，后面讨论}12/7010.2插入排序（1）直接插入排序（2）折半插入排序（3）希尔排序有序区无序区一个一个地插入基本思路不是全局有序，全局有序区中的元素在后面排序中不再发生位置的改变主要的插入排序方法：13/7010.2.1直接插入排序1.排序思路有序区R[0]

……

R[i-1]无序区

R[i]

……

R[n-1]有序区R[0]……

R[i-1]

R[i]无序区R[i+1]

……

R[n-1]一趟排序初始时，有序区只有一个元素R[0]i＝1~n-1，共经过n-1趟排序14/70jR[i]j=i-1插入位置一趟直接插入排序：在有序区中插入R[i]的过程。有序区R[0..i-1]R[j+1]=tmptmp使R[0..i]有序扩大有序区R[j]大时便后移当R[i].key<R[i-1].key时15/70

【例10.1】设待排序表有10个元素，其关键字序列为（9，8，7，6，5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。初始

[9]

8 7 6 5 4 3 2 1 0i=1：

[8 9]

7 6 5 4 3 2 1 0i=2：

[7 8 9]

6 5 4 3 2 1 0i=3：

[6 7 8 9]

5 4 3 2 1 0i=4：

[5 6 7 8 9]

4 3 2 1 0i=5：

[4 5 6 7 8 9]

3 2 1 0i=6：

[3 4 5 6 7 8 9]

2 1 0i=7：

[2 3 4 5 6 7 8 9]

1 0i=8：

[1 2 3 4 5 6 7 8 9]

0i=9：

[0 1 2 3 4 5 6 7 8 9]16/70直接插入排序动画17/70publicvoidInsertSort(){ //对R[0..n-1]递增排序RecTypetmp;intj;for(inti=1;i<n;i++){ //从第2个元素即R[1]开始if(R[i].key<R[i-1].key){ //反序时tmp=R[i]; //取出无序区的第一个元素j=i-1; //有序区中从右向左找R[i]插入位置

do{R[j+1]=R[j]; //关键字大于tmp.key的元素后移j--; //继续向前比较}while(j>=0&&R[j].key>tmp.key);R[j+1]=tmp; //在j+1处插入R[i]}}}2.排序算法18/703.算法分析1）最好情况分析初始数据序列正序最好情况下的时间复杂度为O(n)。19/702）最坏情况分析初始数据序列反序最坏情况下的时间复杂度为O(n2)。20/703）平均情况分析将R[i]插入到R[0..i-1]（含i个元素）的中间位置平均情况的时间复杂度为O(n2)。21/7010.2.2折半插入排序1.排序思路查找采用折半查找方法，称为二分插入排序或折半插入排序。有序区R[0]……

R[i-1]无序区R[i]

……

R[n-1]采用折半查找在有序区找到插入的位置22/70publicvoidBinInsertSort(){ //对R[0..n-1]按递增有序进行折半插入排序intlow,high,mid;RecTypetmp;for(inti=1;i<n;i++){if(R[i].key<R[i-1].key){ //反序时tmp=R[i]; //将R[i]保存到tmp中low=0;high=i-1;while(low<=high){ //在R[low..high]中折半查找插入位置mid=(low+high)/2; //取中间位置if(tmp.key<R[mid].key)high=mid-1; //插入点在左区间elselow=mid+1; //插入点在右区间}for(intj=i-1;j>=high+1;j--) //元素集中后移R[j+1]=R[j];R[high+1]=tmp; //插入原来的R[i]}}}2.排序算法折半查找与GOEk算法类似23/703.算法分析在任何情况下排序中元素移动的次数与直接插入排序的相同，不同的仅是变分散移动为集中移动。平均情况的时间复杂度为O(n2)。24/70说明：本题为2012年全国考研题

【例（补充）】对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A.排序的总趟数

B.元素的移动次数C.使用辅助空间的数量

D.元素之间的比较次数25/7010.2.3希尔排序1.排序思路{R[0]，R[d]，R[2d]，…，R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}

…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}例如：将n个元素分成d个组：相距d个位置的元素分为一组一组一组一组26/70

d=n/2将排序序列分为d个组，在各组内进行直接插入排序递减d=d/2，重复②，直到d=0算法最后一趟对所有元素进行了直接插入排序，所以结果一定是正确的。27/70

【例10.2】设待排序的表有10个元素，其关键字分别为（9，8，7，6，5，4，3，2，1，0）。说明采用希尔排序方法进行排序的过程。9876543210初始序列8765943210d=53210直接插入排序498765d=d/2=243210987650123456789直接插入排序d=d/2=10123456789直接插入排序0123456789对于d=1的一趟，排序前的数据已将近正序！28/70希尔排序动画29/702.排序算法取d1=n/2，di+1=

di/2

时的希尔排序的算法publicvoidShellSort() //对R[0..n-1]按递增有序进行希尔排序{RecTypetmp;intd=n/2; //增量置初值while(d>0){for(inti=d;i<n;i++) //对相隔d位置的元素组采用直接插入排序{tmp=R[i];intj=i-d;while(j>=0&&tmp.key<R[j].key){R[j+d]=R[j]; //对相隔d位置的元素组排序j=j-d;}R[j+d]=tmp;}d=d/2; //递减增量}}30/703.算法分析d1=n/2，di+1=

di/2

（i≥1），也就是说，每趟后一个增量是前一个增量的1/2，则经过t=

log2n

-1趟后dt=1，再经过一趟最后直接插入排序使整数数序变为有序的。希尔算法的时间复杂度难以分析，一般认为其平均时间复杂度为O(n1.58)。希尔排序的速度通常要比直接插入排序快。31/70直接插入排序大约时间=102=100希尔排序d=5：分为5组，时间约为5×22＝20d=2：分为2组，时间约为2×52＝50d=1：分为1组，几乎有序，时间约为10＋＋＝80例如：有10个元素要排序。32/70希尔排序是一种不稳定的排序算法第1组排序结果378102012568第2组排序结果d=2趟排序结果317285106208相对位置发生改变351087281206n=10,d=5一般地，相距位置较大的两个元素发生交换

不稳定！33/7010.3交换排序两个元素反序时进行交换基本思路（1）冒泡排序（2）快速排序主要的交换排序方法：34/7010.3.1冒泡排序1.排序思路有序区R[0]┇R[i-1]无序区R[i]R[i+1]┇R[n-1]将无序区中最小元素放在R[i]有序区R[0]┇R[i-1]R[i]无序区R[i+1]┇R[n-1]一趟排序初始有序区为空。i＝0~n-2，共n-1趟使整个数据有序。R[i]有序区总是全局有序的35/70

【例10.3】设待排序的表有10个元素，其关键字分别为{9，8，7，6，5，4，3，2，1，0}。说明采用冒泡排序方法进行排序的过程。初始：[]9 8 7 6 5 4 3 2 1 0i=0：

[0] 9 8 7 6 5 4 3 2 1i=1：

[0 1] 9 8 7 6 5 4 3 2i=2： [0 1 2] 9 8 7 6 5 4 3i=3： [0 1 2 3] 9 8 7 6 5 4i=4： [0 1 2 3 4] 9 8 7 6 5i=5： [0 1 2 3 4 5] 9 8 7 6i=6： [0 1 2 3 4 5 6] 9 8 7i=7： [0 1 2 3 4 5 6 7] 9 8i=8： [0 1 2 3 4 5 6 7 8] 936/70冒泡排序动画37/702.排序算法publicvoidBubbleSort(){ //对R[0..n-1]按递增有序进行冒泡排序booleanexchange=false;for(inti=0;i<n-1;i++){

exchange=false; //本趟前将exchange置为falsefor(intj=n-1;j>i;j--){ //一趟中找出最小关键字的元素if(R[j].key<R[j-1].key){ //反序时交换swap(j,j-1); //R[j]与R[j-1]进行交换

exchange=true; //本趟发生交换置exchange为true}}if(!exchange)return; //本趟没有发生交换，中途结束算法}}38/703.算法分析1）最好情况分析初始数据序列正序最好情况下的时间复杂度为O(n)。39/702）最坏情况分析初始数据序列反序最坏情况下的时间复杂度为O(n2)。40/703）平均情况分析算法可能在中间的某一趟排序完成后就结束，但平均的排序趟数仍是O(n)。每一趟的关键字比较次数和元素移动次数为O(n)，所以平均时间复杂度为O(n2)。平均情况的时间复杂度为O(n2)。41/7010.3.2快速排序1.排序思路1960年发布了使他闻名于世的快速排序算法（QuickSort），这个算法也是当前世界上使用最广泛的算法之一领导了Algol60第一个商用编译器的设计与开发从1977年开始，TonyHoare博士任职于牛津大学，投身于计算系统的精确性的研究、设计及开发1980年获得图灵奖2000年Hoare因为其在计算机科学与教育上做出的贡献被封为爵士。42/70无序的记录序列无序子序列

无序子序列

基准一次划分分别进行快速排序

每趟使表的第1个元素放入适当位置（归位），将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出口）。基准43/70对无序区R[s..t]快速排序的递归模型如下：f(R，s，t)≡

不做任何事情

当R[s..t]为空或者仅有一个元素时f(R，s，t)≡

划分后基准位置为i;其他情况 f(R，s，i-1);f(R，i+1，t);44/702.排序算法1）划分算法设计R[s]

R[s+1]…

R[t-1]R[t]ijbasej从后向前找一个小于base的元素R[j]i从前向后找一个大于base的元素R[i]交换直到i=j，再将基准R[s]和R[i]交换方法145/70③3①5124base3②12354i46/70publicintPartition1(ints,intt){//划分算法1RecTypebase=R[s]; //以表首元素为基准inti=s,j=t;while(i<j) { //从表两端交替向中间遍历,直至i=j为止while(i<j&&R[j].key>=base.key)j--; //从后向前遍历,找一个小于基准的R[j]while(i<j&&R[i].key<=base.key)i++; //从前向后遍历,找一个大于基准的R[i]if(i<j)swap(i,j); //将R[i]和R[j]进行交换}swap(s,i); //将基准R[s]和R[i]进行交换returni;}47/70消除重复比较后的更优算法如下：publicintPartition1_1(ints,intt){//改进划分算法1intbase=R[s].key; //以表首元素为基准,base存放基准关键字inti=s,j=t+1;while(true){ //从表两端交替向中间遍历while(R[++i].key<base) //从前向后遍历,找一个大于等于基准的R[i]if(i==t)break;while(R[--j].key>=base) //从后向前遍历,找一个小于基准的R[j]if(j==s)break;if(i>=j)break;swap(i,j); //将R[i]和R[j]进行交换}swap(s,j); //将基准R[s]和R[j]进行交换returnj; //a[s..j-1]<=a[j]<=a[j+1..t]}n个元素共比较n-1次说明48/70R[s]

R[s+1]…

R[t-1]R[t]ijbasej从后向前找一个小于base的元素R[j]，前移到R[i]，i++i从前向后找一个大于base的元素R[i],后移到R[j],j--直到i=j，再将基准base放在R[i]方法249/70⑤④③3①5124base3②21354in个元素共比较n-1次说明50/70privateintPartition2(ints,intt) //划分算法2{inti=s,j=t;RecTypebase=R[s]; //以表首元素为基准while(i!=j) //从两端交替向中间遍历,直至i=j为止{while(j>i&&R[j].key>=base.key)j--; //从后向前遍历,找一个小于基准的R[j]if(j>i){R[i]=R[j]; //R[j]前移覆盖R[i]i++;}while(i<j&&R[i].key<=base.key)i++; //从前向后遍历,找一个大于基准的R[i]if(i<j){R[j]=R[i]; //R[i]后移覆盖R[j]j--;}}R[i]=base; //基准归位returni; //返回归位的位置}51/70为什么Partition2比Partition1好？减少了元素移动次数！这里是根据base分为两组，两组的元素交换两组的元素个数相同52/70两个组交换位置53/70两个组交换位置②①③3次移动3次移动3次移动共9次移动54/70两个组交换位置②①共7次移动③④⑤⑥⑦55/70初始时，“≤base的区间”含as

i=s，j从s+1开始遍历，“>base的区间”是a[i+1..j-1]若a[j]>base，跳过，j++。若a[j]<=base，i增加1扩大“≤base的区间”，将a[j]与a[i]交换，扩大“>base的区间”，j++。

xxxxaj

…

at≤base的区间as

…

ai>base的区间方法3n个元素共比较n-1次说明56/70

xxxx

…x≤base的区间as

…

ai>base的区间遍历完毕交换

基准归位《算法导论》的思路（以尾元素为基准）57/70publicintPartition3(ints,intt){ //划分算法3inti=s,j=s+1;RecTypebase=R[s]; //以表首元素为基准while(j<=t){ //j从s+1开始遍历其他元素if(R[j].key<=base.key){ //找到小于等于基准的元素R[j]i++; //扩大小于等于base的元素区间if(i!=j)

swap(i,j); //将R[i]与R[j]交换}j++; //继续扫描}swap(s,i); //将基准R[s]和R[i]进行交换returni;}58/702）排序算法设计f(R，s，t)≡

不做任何事情

当R[s..t]为空或者仅有一个元素时f(R，s，t)≡

划分后基准位置为i;其他情况 f(R，s，i-1);f(R，i+1，t);publicvoidQuickSort(){//对R[0..n-1]按递增进行快速排序QuickSort1(0,n-1);}privatevoidQuickSort1(ints,intt) {//对R[s..t]的元素进行快速排序if(s<t){ //表中至少存在两个元素的情况inti=Partition*(s,t); //可用前面3种划分算法中的任意一种

QuickSort1(s,i-1); //对左子表递归排序

QuickSort1(i+1,t); //对右子表递归排序}}59/70《算法导论》的动画（以尾元素为基准）60/70

【例10.4】设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用快速排序方法进行排序的过程。快速排序过程

递归树61/706

87

9

0

1

3

2455

423019

7861

423

050，1，2，3，4，5，6，7，8，902

3

413

42348

7978将递归树看成一颗3叉树，每个分支结点对应一次递归调用。这里递归次数：7左右分区处理的顺序无关62/703.算法分析1）最好情况分析

如果初始数据序列随机分布，使得每次划分恰好分为两个长度相同的子表，此时递归树的高度最小，性能最好。最好情况下的时间复杂度为O(nlog2n)。47563122134657567123log2(n+1)63/702）最坏情况分析

如果初始数据序列正序或者反序，使得每次划分的两个子表中一个为空一个长度为n-1，此时递归树的高度最高，性能最差。最坏情况下的时间复杂度为O(n2)。12345672345671345672…n64/703）平均情况分析平均情况的时间复杂度为O(nlog2n)。n个元素无序区一次划分k-1个元素n-k个元素无序区无序区R[i]归位k：1～n65/70【例10.5】设计一个以排序序列的中间位置元素为基准的快速排序算法。

对于排序序列R[s..t]，当其中个数大于1时，其中间位置mid=(s+t)/2，将首元素R[s]与R[mid]交换，再采用以首元素为基准的一般快速排序方法。66/70privatevoidQuickSort2(ints,intt){if(s<t){ //表中至少存在两个元素的情况intmid=(s+t)/2;swap(s,mid); //R[s]与R[mid]交换inti=Partition*(s,t); //可以使用前面3种划分算法中任意一种

QuickSort2(s,i-1); //对左子表递归排序

QuickSort2(i+1,t); //对右子表递归排序}}67/70

已知由n（n≥2）个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C、C++描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。2016年全国计算机学科专业考研题扩展68/70

思路：将最小的

n/2个元素放在A1中，其他放在A2中查找第n/2小的元素递归快速排序69/70intSolution(int[]a,intn){ //求解算法intlow=0,high=n-1;boolflag=true;while(flag){inti=Partition*(a,low,high); //可以使用前面3种划分算法中任意一种if(i==n/2-1) //基准a[i]为第n/2的元素

flag=false;elseif(i<n/2-1) //在右区间查找

low=i+1;elsehigh=i-1; //在左区间查找

}ints1=0,s2=0;for(inti=0;i<n/2;i++)s1+=a[i];for(intj=n/2;j<n;j++)s2+=a[j];returns2-s1;}时间复杂度为O(n)70/7010.4选择排序（1）简单选择排序（2）堆排序基本思路主要的选择排序方法：全局有序区无序区选出最小元素R[k]71/3710.4.1简单选择排序1.排序思路

从一个无序区中选出最小的元素，最简单方法是逐个进行元素比较，例如，从无序区R[i..n-1]中选出最小元素R[minj]。intminj=i; //minj先置为区间中的首元素序号for(intj=i+1;j<n;j++) //从R[i..n-1]中选最小元素的R[minj]if(R[j].key<R[minj].key)minj=j;简单选择72/37有2n个整数，找到其中最大整数需要比较次数最少是（）次。A.n B.log2n C.n2D.2n E.2n-1 F.n-1示例73/37全局有序区R[0]

……

R[i-1]无序区R[i]

……

R[n-1]全局有序区R[0]

……

R[i-1]R[i]无序区R[i+1]

……

R[n-1]采用简单选择方法选出最小元素初始时，全局有序区为空i＝0~n-2，共经过n-1趟排序74/372.排序算法publicvoidSelectSort(){ //对R[0..n-1]元素进行简单选择排序RecTypetmp;for(inti=0;i<n-1;i++){ //做第i趟排序intminj=i;for(intj=i+1;j<n;j++) //无序区R[i..n-1]中选最小元素R[minj]if(R[j].key<R[minj].key)minj=j;if(minj!=i) //R[minj]不是无序区首元素swap(i,minj); //交换R[i]和R[minj]}}75/37

【例10.6】设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用简单选择排序方法进行排序的过程。初始关键字 []6 8 7 9 0 1 3 2 4 5i=0的结果： [0] 8 7 9 6 1 3 2 4 5i=1的结果： [0 1] 7 9 6 8 3 2 4 5i=2的结果： [0 1 2] 9 6 8 3 7 4 5i=3的结果： [0 1 2 3] 6 8 9 7 4 5i=4的结果： [0 1 2 3 4] 8 9 7 6 5i=5的结果： [0 1 2 3 4 5] 9 7 6 8i=6的结果： [0 1 2 3 4 5 6] 7 9 8i=7的结果： [0 1 2 3 4 5 6 7] 9 8i=8的结果： [0 1 2 3 4 5 6 7 8] 976/3777/363.算法分析

无论初始数据序列的状态如何，在第i趟排序中选出最小元素，内for循环需做n-1-(i+1)+1=n-i-1次比较，因此，总的比较次数为78/37元素的移动次数当初始数据序列正序时，移动次数为0。反序时每趟排序均要执行交换操作，此时总的移动次数为最大值3(n-1)。最好、最坏和平均情况的时间复杂度均为O(n2)。79/37是一种不稳定的排序方法（5，

5，1）无序区交换（1，5，5）80/3710.4.2堆排序1.排序思路全局有序区无序区选出最小元素R[k]采用堆方法选出最小元素：堆排序算法81/37一个序列R[1..n]，关键字分别为k1、k2、、kn。堆的定义该序列满足如下性质（简称为堆性质）：

ki≤k2i

且ki≤k2i+1

或

ki≥k2i

且ki≥k2i+1 （1≤i≤

n/2）满足第

种情况的堆称为小根堆，满足第

种情况的堆称为大根堆。下面讨论的堆是大根堆。82/37a1a2a3an…完全二叉树i2i2i+1左孩子右孩子大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字。最小关键字的元素一定是某个叶子结点！！！层序编号方式：a1

a2

…

an

将序列a1

a2

…

an看成是一颗完全二叉树83/371295413n=6如何判断一颗完全二叉树是否为大根堆124356从编号为n/2=3的结点开始，逐一判断所有分支结点所有分支结点满足定义

大根堆84/37

堆排序的关键是构造堆，这里采用筛选算法建堆。

所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选堆筛选2.排序算法85/37是一个堆是一个堆295413

筛选：不是堆

堆从根开始筛选大根堆tmp86/37295413从根开始筛选直接插入排序思路87/36仅仅处理从根结点

某个叶子结点路径上的结点n个结点的完全二叉树高度为

log2(n+1)

所有筛选的时间复杂度为O(log2n)295413从根开始筛选88/37low2*low2*low+1……high…筛选算法sift(RecType[]R，intlow，inthigh)：R[low..high]R[low..high]根最后结点89/37privatevoidsift(intlow,inthigh){ //对R[low..high]进行筛选inti=low,j=2*i; //R[j]是R[i]的左孩子RecTypetmp=R[i]; //tmp临时保存根结点while(j<=high){ //只对R[low..high]的元素进行筛选if(j<high&&R[j].key<R[j+1].key) j++; //若右孩子较大,把j指向右孩子if(tmp.key<R[j].key){ //tmp的孩子较大R[i]=R[j]; //将R[j]调整到双亲位置上i=j;j=2*i; //修改i和j值,以便继续向下筛选}elsebreak; //若孩子较小，则筛选结束}R[i]=tmp; //原根结点放入最终位置}90/37

一颗完全二叉树

初始堆435216124356例如，序列：（4，3，5，2，1，6），n=6从编号为n/2=3的结点开始，逐一筛选65546初始堆:（6，3，5，2，1，4）for(i=n/2;i>=1;i--)//循环建立初始堆

sift(i，n);最大元素筛选步骤：sift(3，6)sift(2，6)sift(1，6)91/37635214124356

最大元素归位4，3，5，2，1，6最大元素6归位R[1]R[i]4352112435654R[1]R[i-1]再对R[1..i-1]的元素进行筛选92/37堆排序算法：publicvoidHeapSort(){ //对R[1..n]按递增进行堆排序for(inti=n/2;i>=1;i--) //循环建立初始堆sift(i,n); //对R[i..n]进行筛选for(inti=n;i>=2;i--){ //进行n-1趟排序,每一趟排序的元素个数减1swap(1,i); //将区间中最后一个元素与R[1]交换

sift(1,i-1); //从R[1]继续筛选,得到i-1个结点的堆}}93/37

【例10.7】设待排序的表有10个元素，其关键字分别为{6，8，7，9，0，1，3，2，4，5}。说明采用堆排序方法进行排序的过程。排序序列：6，8，7，9，0，1，3，2，4，58952401376看成是一棵完全二叉树94/37调整成初始大根堆：8952401376调整完毕，成为一个大根堆987651324095/378602451379输出9（归位）从根结点筛选6420513780876513249第1趟排序96/37642051378输出8（归位）从根结点筛选642510370674513289第2趟排序其他各趟排序依此进行0123456789最终结果：97/37

对高度为h的堆，一次“筛选”所需进行的关键字比较的次数至多为2(h-1)。

调整“堆顶”n-1次，总共进行的关键字比较的次数不超过：

2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

对n个关键字，建成高度为h（=

log2n+1）的堆，所需进行的关键字比较的次数不超过4n。3.算法分析堆排序的时间复杂度为O(nlogn)。空间复杂度为O(1)，不稳定。98/37设有1000个无序的整数，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序方法。A.冒泡排序 B.简单选择排序C.堆排序 D.直接插入排序n=1000，k=10冒泡排序的大致时间：kn堆排序的大致时间：4n+klog2n。示例99/37数据结构经典算法的启示简单选择排序算法堆排序算法利用了连续多次查找最大元素的特性优先队列就是采用堆实现的！100/3610.4.3堆数据结构线性表voidpush(Ee)：向堆中插入元素e。Epop()：删除一个元素并且返回该元素。这里的删除运算仅仅删除非空队的堆顶元素。booleanempty()：判断堆是否为空。用R[1..n]存放一个堆，即（R，n）101/371.插入运算算法设计85632（a）一个大根堆85632（b）末尾添加1010810632（c）10与双亲交换5108632（d）10与双亲交换5102/37插入运算：作为叶子结点插入到末尾，从该位置先上筛选变为大根堆。publicvoidpush(RecTypee){ //插入元素en++; //堆中元素个数增1R[n]=e; //将e添加到末尾if(n==1)return; //e作为根结点的情况intj=n,i=j/2; //i指向R[j]的双亲while(true){if(R[j].key>R[i].key) //若孩子较大swap(i,j); //两者交换if(i==1)break; //到达根结点时结束j=i;i=j/2; //继续向上调整}}103/372.删除运算算法设计在堆中只能删除非空堆的堆顶元素，即最大元素。删除运算：先用e存放堆顶元素，用堆中末尾元素覆盖堆顶元素，执行n--减少元素元素，采用堆排序中的筛选算法调整为一个堆，最后返回e。104/37publicRecTypepop(){ //删除堆顶元素if(n==0)returnnull;RecTypee=R[1]; //取出堆顶元素R[1]=R[n]; //用尾元素覆盖R[1]n--; //元素个数减少1

sift(1,n); //筛选为一个堆returne;}105/363.判断堆是否空算法设计publicbooleanempty(){ //判断堆是否为空returnn==0;}106/37优先队列就是采用堆实现的！107/3710.5归并排序基本思路（k路归并）二路归并排序主要的归并排序方法：有序段1有序段2…有序段k新有序段1有序段1有序段2…有序段k新有序段2……108/4110.5.1自底向上的二路归并排序1.排序思路18220

341232616151822034123261611521820341232616115115218203461216321152612161820323412612151618203234底109/4118220

3412326161518220341232616115第1趟21820341232616115218203461216321152612161820323411512612151618203234第2趟第3趟第4趟归并树有清晰的趟数（同一趟产生的归并段优先归并）归并树高度h=log2n+1归并的趟数=h-1平衡归并110/412.排序算法1）二路归并算法基础：将两个位置相邻的有序子序列归并为一个有序序列。有序序列R[low..high]有序子序列R[low..mid]有序子序列R[mid+1..high]R[low..high]111/41privatevoidMerge(intlow,intmid,inthigh){//R[low..mid]和R[mid+1..high]归并为R[low..high]RecType[]R1=newRecType[high-low+1];inti=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标while(i<=mid&&j<=high){//在第1段和第2段均未扫描完时循环if(R[i].key<=R[j].key){//将第1段中的元素放入R1中R1[k]=R[i];i++;k++;}else{ //将第2段中的元素放入R1中R1[k]=R[j];j++;k++;}}while(i<=mid){ //将第1段余下部分复制到R1R1[k]=R[i];i++;k++;}while(j<=high){ //将第2段余下部分复制到R1R1[k]=R[j];j++;k++;}for(k=0,i=low;i<=high;k++,i++) //将R1复制回R中R[i]=R1[k];}空间复杂度为O(high-low+1)112/412）一趟二路归并排序有序子表长度为len

R[0..n-1]中共分为

n/len

个有序的子表段2的尾元素序号i+2len-1<n

是满的（两个段均含len个元素）i+len-1<n-1（或者i+len<n）

剩余两个有序子表否则说明仅剩余一个有序子表（第2段为空），不趟不参与归并R[0..len-1]R[len..2len-1]R[2len..3len-1]R[3len..4len-1]起始i=0起始i=2len段1段2R[i..i+len-1]R[i+len..i+2len-1]起始i=i+2len113/41privatevoidMergePass(intlen){ //一趟二路归并排序inti;for(i=0;i+2*len-1<n;i=i+2*len) //归并len长的两相邻子表

Merge(i,i+len-1,i+2*len-1);if(i+len<n) //余下两个子表,后者长度小于len

Merge(i,i+len-1,n-1); //归并这两个子表}114/413）二路归并排序publicvoidMergeSort1(){ //对R[0..n-1]按递增进行二路归并算法for(intlen=1;len<n;len=2*len) //进行log2n(取上界)趟归并

MergePass(len);}115/413.算法分析二路归并排序中，长度为n的排序表需做

log2n

趟，对应的归并树高度为

log2n

，每趟归并时间为O(n)。时间复杂度的最好、最坏和平均情况都是O(nlog2n)。

log2n

趟每趟为O(n)116/41归并排序过程中每次调用Merge都需要使用局部数组R1，但执行完后其空间被释放，但最后一趟排序一定是全部n个元素参与归并，所以总的辅助空间复杂度为O(n)。1822034123261611521820341232616115218203461216321152612161820323411512612151618203234117/41三路归并的归并树的高度为

log3n

，同样一次三路归并的时间为O(n)，所以三路归并排序的时间复杂度为O(nlog3n)。而nlog3n=nlog2n/log23，即O(nlog3n)=O(nlog2n)，也就是说，三路归并排序与二路归并排序的时间复杂度相同。二路归并多路归并推广扩展118/41119/4110.5.2自顶向下的二路归并排序排序区间是R[s..t]（为大问题），当其长度为0或者1时，本身就是有序的，不做任何处理。否则，其中间位置m，采用相同方法对R[s..m]和R[m+1..t]排好序（分解为两个小问题），再调用前面的二路归并算法Merge(s，m，t)得到整个有序表（合并）。f(R，s，t)≡

不做任何事情

当R[s..t]为空或者仅有一个元素时f(R，s，t)≡

m=(s+t)/2; 其他情况 f(R，s，m);f(R，m+1，t); Merge(s，m，t);120/41publicvoidMergeSort2(){ //对R[0..n-1]按递增进行二路归并算法MergeSort21(0,n-1);}privatevoidMergeSort21(ints,intt){//被MergeSort2调用if(s>=t)return; //R[s..t]的长度为0或者1时返回intm=(s+t)/2; //取中间位置m

MergeSort21(s,m); //对前子表排序

MergeSort21(m+1,t); //对后子表排序

Merge(s,m,t); //将两个有序子表合并成一个有序表}递归二路归并排序方法121/41

【例10.10】设排序序列有5个元素，其关键字分别为（3，5，1，2，4）。说明采用自顶向下二路归并排序方法进行排序的过程。3 5 1 2 4(1)分解3 5 12 4(2)分解3 51(3)分解35(6)分解24(7)合并2 4(4)合并3 5(5)合并1 3 5(8)合并1 2 3 4 5顶122/41

设R[0..n-1]排序的时间为T(n)，当n>1时，MergeSort21(0,n/2)和MergeSort21(n/2+1,n-1)两个子问题的时间均为T(n/2)，而Merge的时间为O(n)。对应的递推式如下：T(n)=1 当n=1T(n)=2T(n/2)+n

当n>1T(n)=O(nlog2n)123/41

设R[0..n-1]排序的空间为S(n)，当n>1时，两个子问题的空间均为S(n/2)，而Merge的空间为O(n)。但MergeSort21(0,n/2)求解完后栈空间释放，被MergeSort21(n/2+1,n-1)重复使用，对应的递推式如下：S(n)=1 当n=1S(n)=S(n/2)+n

当n>1S(n)=O(n)124/41【例10.11】求解POJ1804—参谋问题，时间限制为1000ms，空间限制为30000K。

问题描述：给你n个整数的序列，目标是移动整数以便最后对序列进行排序，允许的唯一操作是交换（swap）两个相邻的整数。例如：

初始序列：2803swap(28)8203swap(20)8023swap(23)8032swap(80)0832swap(83)0382swap(82)0328swap(32)0238swap(38)0283swap(83)0238因此，序列（2803）可以通过9次交换相邻整数得到有序序列。甚至可以3次交换相邻整数得到有序序列：

初始序列：2803swap(80)2083swap(20)0283swap(83)0238该问题是对于给定的序列进行排序，求相邻整数的最小交换次数是多少？125/41

输入格式：第一行为场景数量。对于每个场景，首先给出一行包含序列的长度n（1≤n≤1000），然后是该序列的n个整数（每个整数的范围是[-1000000，1000000]），此行中的所有整数均由单个空格分隔。

输出格式：每个场景的输出以“Scenario#i：”的行开始，其中i是从1开始的场景编号，然后输出一行包含对给定初始序列所需的相邻整数的最小交换数量，使用空行结束每个场景的输出。输入样例：4428031001234567896-4223628-10065537500000输出样例：Scenario#1:3

Scenario#2:0

Scenario#3:5

Scenario#4:0126/41对于一个含n个整数的场景，用数组a存放其整数序列，将其排序所需要的相邻整数的最小交换次数就是a序列的逆序数。例如，对于整数序列（2，8，0，3），有逆序对（2，0），（8，0），（8，3），则逆序数为3。一般地，对于整数序列a=（a0，a1，…，ai，…，aj，…，an-1），逆序对是（ai，aj）满足i<j并且ai>aj，逆序对个数称为a的逆序数。127/41

在a[low..high]递归二路归并排序时，先对前后两半a[low..mid]和a[mid+1..high]分别进行二路归并排序，再将这两半有序序列合并