数据结构-从概念到C++实现（第4版）课件 第七章 排序技术

7-1排序概述v第七章排序技术排序的定义女李爽0005女齐梅0004女刘楠0003男张亮0002男王刚0001性别姓名职工号5635573548年龄1982.92003.71979.92003.71990.4工作时间排序是对线性结构的一种操作排序：给定一组记录的集合{r1,r2,…,rn}，其相应的关键码分别为{k1,k2,…,kn}，将这些记录排列为{rs1,rs2,…,rsn}的序列，使得相应的关键码满足ks1≤ks2≤…≤ksn（或ks1≥ks2≥…≥ksn）。数据元素、结点、顶点升序（非降序）降序（非升序）排序的数据模型是什么？排序码：排序的依据，简单起见，也称关键码。（1）进行升序排序不失一般性，做如下约定：（3）采用顺序存储（即数组）（2）记录只有排序码一个数据项排序的定义女李爽0005女齐梅0004女刘楠0003男张亮0002男王刚0001性别姓名职工号5635573548年龄1982.92003.71979.92003.71990.4工作时间排序是对线性结构的一种操作排序的数据模型是什么？排序码：排序的依据，简单起见，也称关键码。正序、逆序正序：待排序序列中的记录已按关键码排好序。1234512345逆序（反序）：待排序序列中记录的顺序与排好序的顺序相反。5432112345深刻理解趟的含义能够更好地掌握排序方法的思想和过程趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。算法的稳定性排序算法的稳定性：假定在待排序的记录序列中存在多个具有相同关键码的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法稳定，否则称为不稳定。学号姓名高数英语语文0001王军85880002李明64920003汤晓影8586………687278……学号姓名高数英语语文0001王军64880002李明85920003汤晓影8586………687278……排序算法的稳定性只是算法的一种属性，且由具体算法决定排序的分类根据排序过程中所有记录是否全部放在内存中，排序方法分为：（1）内排序：在排序的整个过程中，待排序的所有记录全部放在内存中（2）外排序：待排序的记录个数较多，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果根据排序方法是否建立在关键码比较的基础上，排序方法分为：（1）基于比较：主要通过关键码之间的比较和记录的移动实现（2）不基于比较：根据待排序数据的特点所采取的其他方法①插入排序；②交换排序；③选择排序；④归并排序直接插入排序希尔排序起泡排序快速排序简单选择排序堆排序二路归并递归算法二路归并非递归算法排序算法的性能如何衡量排序算法的性能呢？（1）时间性能：排序算法在各种情况（最好、最坏、平均）下的时间复杂度。例如，基于比较的内排序在排序过程中的基本操作：①比较：关键码之间的比较；②移动：记录从一个位置移动到另一个位置。（2）空间性能：排序过程中占用的辅助存储空间。辅助存储空间是除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。排序类的定义classSort{public:

Sort(intr[],intn);

~Sort();

voidInsertSort();

voidShellSort();

voidBubbleSort();

voidQuickSort(intfirst,intlast);

voidSelectSort();

voidHeapSort();

voidMergeSortRecursion();voidMergeSort(intfirst,intlast);

voidPrint();private:

intPartition(intfirst,intlast);

voidSift(intk,intlast);

voidMerge(intfirst1,intlast1,intlast2);

voidMergePass(inth);

int*data;

intlength;};Sort::Sort(intr[],intn){

data=newint[n];

for(inti=0;i<n;i++)

data[i]=r[i];

length=n;}Sort::~Sort(){

delete[]data;}voidSort::Print(){

for(inti=0;i<length;i++)

{

cout<<data[i]<<"\t";

}

cout<<endl;}排序类的定义classSort{public:

Sort(intr[],intn);

~Sort();

voidInsertSort();

voidShellSort();

voidBubbleSort();

voidQuickSort(intfirst,intlast);

voidSelectSort();

voidHeapSort();

voidMergeSortRecursion();voidMergeSort(intfirst,intlast);

voidPrint();private:

intPartition(intfirst,intlast);

voidSift(intk,intlast);

voidMerge(intfirst1,intlast1,intlast2);

voidMergePass(inth);

int*data;

intlength;};在C++的STL类库中，排序使用函数模板sort，参数是容器的起始位置和结束位置以及一个可选的比较器，函数签名是：voidsort(Iteratorbegin,Iteratorend,Comparatorcmp)7-2插入排序v第七章排序技术学什么？直接插入排序希尔排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-2-1直接插入排序v第七章排序技术基本思想在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序有序区r1r2ri-1……无序区rirnri+1……r'1r'2r'i-1r'i……rnri+1……直接插入排序的基本思想：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都排好序。运行实例2420101812122420101812242010181224201018122420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果如何构造初始的有序序列？242010181212待排序序列for(i=1;i<length;i++){

}将第1个记录看成是初始有序序列，然后从第2个记录起依次插入到有序序列中，直至将第n个记录插入。解决方法：算法描述：插入第i个记录，即第i趟直接插入排序；关键问题如何将第i

个记录插入到有序序列中的合适位置？第一趟排序结果24201018122010182412242010181212待排序序列关键问题242010181212242010181224待排序序列第一趟排序结果第二趟排序结果i在有序序列中进行顺序查找，查找下标初始化为多少？jj=i-1;暂存r[i]关键问题2420101812122420101812241012待排序序列第一趟排序结果第二趟排序结果i在有序序列中进行顺序查找，循环条件是什么？temp=data[i];j=i-1;退出循环，记录r[i]的最终位置是哪里？data[j+1]=temp;算法描述：while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}j关键问题暂存r[i]算法描述voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}时间性能比较语句？执行次数？最好情况：n-1次12345最坏情况：2+3+…+n次12345移动语句？执行次数？最好情况：2(n-1)次12345voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}最坏情况：3+4+…+n+1次12345时间性能时间性能比较次数：n-1移动次数：2(n-1)

最好情况：正序O(n)最坏情况：逆序比较次数：移动次数：平均情况：随机排列O(n2)O(n2)空间性能时间性能

空间性能：O(1)

稳定性：稳定125*454125*455*125*45while(temp<data[j]){data[j+1]=data[j];j--;}7-2-2希尔排序v第七章排序技术改进的着眼点在待排序序列正序时，直接插入排序的时间性能是O(n)。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。（1）若待排序记录按关键码基本有序，直接插入排序的效率较高；改进的着眼点：（2）若待排序记录数量

n

较小，直接插入排序的效率也很高。待排序记录数量n

较大、并不是按关键码基本有序，怎么办？基本思想希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。局部有序（部分有序）不能提高直接插入排序算法的时间性能。基本有序：接近正序，例如{1,2,8,4,5,6,7,3,9}。{5,6,7,8,9,1,2,3,4}是基本有序吗？如何分割待排序序列，才能使整个序列逐步向基本有序发展？如何分割待排序序列，才能使整个序列逐步向基本有序发展？不能是逐段分割，而是将相距某个增量的记录组成一个子序列2408321024*162028123024321624*100812202830基本思想运行实例081024*28321612242030待排序序列增量d=4321612242030081024*28增量d=2321612081024203024*2824203024*2832161008123216120824203024*2810增量d=1关键问题希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。如何分割待排序序列，才能使整个序列逐步向基本有序发展？（1）希尔排序的时间性能取决于增量序列，复杂的数学问题。（2）希尔排序是平均时间性能好于O(n2)的第一批算法之一（1959年）。（3）希尔最早提出的方法是，且增量序列互质。显然最后一个增量必须等于1——缩小增量排序算法效率与增量序列密切相关，练习中一般会给定增量序列for(d=length/2;d>=1;d=d/2){

}算法描述：以d为增量，在每个子序列内进行直接插入排序；关键问题希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。如何分割待排序序列，才能使整个序列逐步向基本有序发展？关键问题081024*28321612242030待排序序列增量d=4081024*28321612242030i在一趟希尔排序中，从哪个记录开始执行插入操作？for(i=d+1;i<length;i++){

}算法描述：将r[i]插入到所属子序列的合适位置；081024*28321612242030待排序序列增量d=4081024*28321612242030ij在相应子序列中进行顺序查找，查找下标初始化为多少？循环条件是什么？1632算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}关键问题081024*28321612242030待排序序列增量d=4081024*28321612242030ij1632退出循环，记录r[i]的最终位置是哪里？data[j+d]=temp;16算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}关键问题验证算法081024*28321612242030待排序序列增量d=4081024*28321612242030ij203216081024*2812242030242032081024*281230直接插入排序时间性能较好分割使得子序列的记录个数较少16算法实现voidSort::ShellSort(){ intd,i,j,temp;for(d=length/2;d>=1;d=d/2)//增量为d进行直接插入排序{for(i=d;i<length;i++)//进行一趟希尔排序{temp=data[i];//暂存待插入记录for(j=i-d;j>=0&&temp<data[j];j=j-d)data[j+d]=data[j];//记录后移d个位置data[j+d]=temp;}}}性能分析（1）希尔排序算法的时间性能是所取增量的函数；

时间性能：O(n2)~

O(nlog2n)

稳定性：不稳定081024*28321612242030待排序序列增量d=4321612242030081024*28

空间性能：O(1)——暂存单元（2）研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间；（3）如果选定合适的增量序列，希尔排序的时间性能可以达到O(n1.3)。增量d=3?5?7-3交换排序v第七章排序技术学什么？起泡（冒泡）排序快速排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-3-1起泡排序v第七章排序技术基本思想无序区r1r2ri-1…有序区rirnri+1…起泡排序的基本思想：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。反序则交换类似水中的气泡，体积大的浮到上面，起泡排序（冒泡排序）因而得名运行实例2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1210201824241012182024101218202410121820第二趟排序有必要吗？88888第五趟排序结果24101218208第四、五趟排序有必要吗？关键问题2420101812待排序序列第一趟排序结果1210182024如果有多个记录位于最终位置，如何不参加下一趟排序？if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}设置变量exchange记载交换的位置，一趟排序后exchange记载的就是最后交换的位置，从exchange之后的记录不参加下一趟排序。解决方法：算法描述：交换交换2420101812待排序序列第一趟排序结果2024下一趟排序的范围是多少？bound=exchange;exchange=0;for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}设置变量bound表示一趟起泡排序的范围[1,bound]，并且bound与上一趟起泡排序的最后交换的位置exchange之间的关系是bound=exchange。解决方法：算法描述：交换交换121018关键问题某趟排序结果下一趟排序结果2024如何判别起泡排序的结束？while(exchange!=0){

执行一趟起泡排序；}一趟排序没有交换，则表明整个序列已经有序。解决方法：算法描述：1210182024121018关键问题算法实现voidSort::BubbleSort(){ intj,exchange,bound,temp;exchange=length-1;while(exchange!=0){bound=exchange;exchange=0；

for(j=0;j<bound;j++)if(data[j]>data[j+1]){temp=data[j];data[j]=data[j+1];data[j+1]=temp;

exchange=j；//记载每一次记录交换的位置

}}}比较语句？执行次数？移动语句？执行次数？取决于待排序序列的初始状态时间性能性能分析比较次数：n-1

移动次数：0

12345最好情况：正序O(n)最坏情况：逆序O(n2)比较次数：

移动次数：平均情况：随机排列O(n2)51432

空间性能：O(1)

稳定性：稳定if(data[j]>data[j+1]){

temp=r[j];r[j]=r[j+1];r[j+1]=temp

exchange=j；}7-3-2快速排序v第七章排序技术改进的着眼点5143245352551记录的比较在相邻单元中进行每次交换只能右移一个单元总的比较次数和移动次数较多较大记录从前面直接移到后面，较小记录从后面直接移到前面？基本思想快速排序的基本思想：选一个轴值，将待排序记录划分成两部分，左侧记录均小于或等于轴值，右侧记录均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。均≤ri'r1'ri-1'…ri'rn'ri+1'…r1ri-1…rirnri+1…均≥ri'运行实例10283216242030待排序序列第一趟排序结果第二趟排序结果第三趟排序结果102832162420301028321620301028322010283216242030最终排序结果关键问题如何选择轴值？选取不同轴值有什么后果?决定两个子序列的长度决定排序的时间性能解决方法：（1）第一个记录；（2）随机选取；（3）三数取中：取三个记录的中值；不失一般性，取第一个记录作为轴值10283216242030待排序序列10283216242030一次划分结果一次划分：以轴值为基准将无序序列划分为两部分如何实现一次划分——较大的记录移到后面，较小记录移到前面？记录的比较和移动从两端向中间进行较小的记录一次就能从后面移到前面（较大的记录？）减少了总的比较次数和移动次数关键问题10283216242030待排序序列10283216242030一次划分结果运行实例10283216242030待排序序列jij从后向前扫描直到r[j]<r[i]10283216242030ji交换r[j]和r[i]，i++10283216242030待排序序列j从后向前扫描直到r[j]<r[i]10283216242030ji交换r[j]和r[i]，i++i从前向后扫描直到r[j]<r[i]交换r[j]和r[i]，j--10283216242030ji重复上述过程，直到i等于j运行实例算法实现intSort::Partition(intfirst,intlast){ inti=first,j=last,temp;while(i<j) {}retutni;/*i为轴值记录的最终位置*/}为什么设置形参first和last？表示什么？1028321624203010283216242030表示待划分区间[first,last]，是变化的jiintSort::Partition(intfirst,intlast){ inti=first,j=last,temp;

while(i<j) {}

retutni;

}

while(i<j&&data[i]<=data[j])j--；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;i++;}

while(i<j&&data[i]<=data[j])i++；if(i<j){temp=data[i];data[i]=data[j];data[j]=temp;j--;}算法实现时间性能时间复杂度是多少？下标i和j共同将数组扫描一遍比较语句？执行次数？移动语句？执行次数？取决于待排序序列的初始状态O(n)10283216242030待排序序列10283216242030如何处理一次划分得到的两个待排序子序列？解决方法：递归执行快速排序一次划分结果voidSort::QuickSort(intfirst,intlast){intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}算法描述：关键问题10283216242030待排序序列第一趟排序结果第二趟排序结果10283216242030102832162030何时结束递归？解决方法：若待排序序列只有一个记录，即待划分区间长度为1if(first>=last)return;关键问题voidSort::QuickSort(intfirst,intlast){ }else{intpivot=Partition(first,last);QuickSort(first,pivot-1);QuickSort(pivot+1,last);}if(first>=last)return;算法实现性能分析12345最好情况：每次划分的轴值均是中值O(nlog2n)67排序趟数：log2n一趟排序：O(n)最坏情况：正序、逆序排序趟数：n-1一趟排序：O(n)O(n2)O(nlog2n)1234567平均情况：随机排列

空间性能：O(log2n)~O(n)一次划分：O(1)递归深度：O(log2n)~O(n)

稳定性：不稳定7-4选择排序v第七章排序技术学什么？简单选择排序堆排序提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-4-1简单选择排序v第七章排序技术基本思想有序区无序区min简单选择排序的基本思想：第

i

趟（1≤i≤n-1）排序在待排序序列ri~rn

中选取最小记录，并和第

i个记录交换。r1ri-1…rirn……r1ri-1…ri'ri+1rn…运行实例2420101812待排序序列第一趟排序结果第二趟排序结果第三趟排序结果第四趟排序结果1012242018122420181018241220102018241210关键问题简单选择排序进行多少趟？for(i=0;i<length-1;i++){

}算法描述：第i趟简单选择排序；有序区无序区minr1ri-1…rirn……第i

趟简单选择排序完成什么工作？（1）在r[i]~r[n-1]中找最小值（2）将最小记录与r[i]交换算法描述：

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;if(index!=i)data[i]<==>data[index];算法实现voidSort::SelectSort(){inti,j,index,temp;for(i=0;i<length-1;i++) {

}}

if(index!=i){temp=data[i];data[i]=data[index];data[index]=temp;}

index=i; for(j=i+1;j<length;j++)if(data[j]<data[index])index=j;交换语句之前的判断一定会提高效率吗？比较语句？执行次数？移动语句？执行次数？时间性能与排序数据的初始状态有关性能分析最好情况：0次最坏情况：3(n-1)次比较次数：O(n2)移动次数：12345最好、最坏、平均情况：O(n2)12345

空间性能：O(1)

稳定性：不稳定155*155*7-4-2堆排序v第七章排序技术改进的着眼点缺点：简单选择排序的时间主要耗费在哪了呢？第i

趟扫描无序序列（n-i

次比较）只做了一件事——找最小值改进的着眼点：利用简单选择排序的思想，同时减少比较次数利用每趟比较后的结果优点：移动次数较少，最坏情况O(n)查找最小值的同时找出并保存较小值减少后面选择所用的比较次数提高整个排序的效率堆的定义小根堆：每个结点的值都小于等于其左右孩子结点的完全二叉树。大根堆：每个结点的值都大于等于其左右孩子结点的完全二叉树。小根堆和大根堆统称为堆。1820323825365040284550384532364020182828堆的特点50384532364020182828（2）较大值的结点靠近根结点，但不绝对。大根堆有什么特点呢？（1）根结点（称为堆顶）的值是所有结点的最大值；将堆按层序编号，有什么特点？12367541098堆与序列的关系5038453236402018282812367541098堆采用顺序存储，则对应一个（无序）序列503845323640282018280123456789顺序存储data[i]左孩子data[2*i+1]右孩子data[2*i+2]双亲与左右孩子之间的关系？堆调整堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，调整根结点使整个完全二叉树成为一个堆的过程。voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}如何设计函数接口？由于初始建堆和重建堆均调用此函数，因此，设置形参k和last关键问题283632251816362832251816iji和j的关系是？inti=k,j=2*i+1;j是i的左孩子voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}循环条件是？283632301816362832301816363032281816

while(j<=last){}ijijiinti=k,j=2*i+1;voidSort::Sift(intk,intlast)//根结点的编号为k，最后一个结点的编号为last{}关键问题28为什么和36交换？

if(j<last&&data[j]<data[j+1])j++;交换后如何调整i和j？else{

temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;}283632301816362832301816363032281816ijiji

while(j<=last){

}

if(j<last&&data[j]<data[j+1])j++;if(data[i]>data[j])break;什么时候结束筛选？关键问题堆调整算法voidSort::Sift(intk,intlast){inti,j,temp;i=k;j=2*i+1;//i是被调整结点，j是i的左孩子while(j<=last)//还没有进行到叶子{if(j<last&&data[j]<data[j+1])j++;//j指向左右孩子的较大者if(data[i]>data[j])break;//已经是堆else{temp=data[i];data[i]=data[j];data[j]=temp;i=j;j=2*i+1;//被调整结点位于结点j的位置}}}基本思想堆排序的基本思想：首先将待排序序列构造成一个大根堆，即选出了堆中所有记录的最大者，将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。r1…rirn…rn-i+1无序区，调整为大根堆有序区第i

趟堆排序将r1~ri

调整成大根堆，再将堆顶与ri

交换运行实例12345待排序序列初始建堆541325413254132541325413254132交换r[1]和r[5]无序区重建堆交换r[1]和r[4]无序区重建堆交换r[1]和r[3]541324312312最后一趟5413221初始建堆如何将一个无序序列建成一个大根堆——初始建堆？待排序序列{28,25,16,36,18,32}282516361832362832251816初始建堆结果{36,28,32,25,18,16}解决办法：从编号最大的分支结点到根结点进行调整算法描述：for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//调整结点i需要调整叶子结点吗？运行实例待排序序列{28,25,16,36,18,32}282516361832282532361816283632251816362832251816初始建堆结果{36,28,32,25,18,16}for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);//调整结点i关键问题12345待排序序列初始建堆5413254132如何处理堆顶——无序区中的最大值？解决办法：交换data[0]与

data[length-i];52交换413241352413如何将无序区重新调整成为大根堆？无序区最后一个结点的编号？解决办法：调整根结点算法描述：Sift(0,length-i-1);52第一趟堆排序结果413431252重建堆结果413关键问题堆排序要进行多少趟？n-1趟算法描述：for(i=0;i<length;i++){

第i

趟堆排序}52第一趟堆排序结果41352重建堆结果413第二趟堆排序结果52413关键问题算法实现voidSort::HeapSort(){inti,temp;for(i=ceil(length/2)-1;i>=0;i--)Sift(i,length-1);for(i=1;i<length;i++){temp=data[0];data[0]=data[length-i];data[length-i]=temp;Sift(0,length-i-1);}}性能分析初始建堆：O(nlog2n)重建堆：O(log2i)最好、最坏、平均情况：O(nlog2n)重建堆次数：n-1

空间性能：O(1)

稳定性：不稳定7-5归并排序v第七章排序技术学什么？二路归并排序的递归实现二路归并排序的非递归实现提出关键问题给出解决方法写出算法描述得到完整算法运行实例7-5-1二路归并排序的递归实现v第七章排序技术基本思想二路归并排序的基本思想：将待排序序列划分为两个长度相等的子序列，分别对这两个子序列进行排序，得到两个有序子序列，再将这两个有序子序列合并成一个有序序列。r1rn/2…rn…rn/2+1划分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤运行实例2420101812待排序序列16划分242010181216分别排序101224161820合并101216182024一次合并：合并两个相邻的有序子序列20254050152130合并可以就地进行吗？ijk

temp[]15

算法描述：while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}first1last1last1+1last2data[]关键问题如何表示两个相邻的子序列？某个子序列比较完毕，做什么？算法描述：while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];202130

4050

算法实现voidSort::Merge(intfirst1,intlast1,intlast2){int*temp=newint[length];inti=first1,j=last1+1,k=first1;while(i<=last1&&j<=last2){if(data[i]<=data[j])temp[k++]=data[i++];elsetemp[k++]=data[j++];}while(i<=last1)temp[k++]=data[i++];while(j<=last2)temp[k++]=data[j++];for(i=first1;i<=last2;i++)data[i]=temp[i];delete[]temp;}递归算法voidSort::MergeSortRecusion(intfirst,intlast){if(first==last)return;else{intmid=(first+last)/2;MergeSort1(first,mid);MergeSort1(mid+1,last);Merge(first,mid,last);}}r1rn/2…rn…rn/2+1划分r1'rn/2'≤…

≤rn'rn/2+1'≤…

≤r1''rn/2''≤…

≤rn''rn/2+1''≤…

≤≤7-5-2

二路归并排序的非递归实现v第七章排序技术执行过程252040153010182025251540203010181540103018待排序序列第一趟归并结果第二趟归并结果第三趟归并结果1520254010183010151820253040构造初始有序子序列子序列长度有什么规律？在一趟归并中有几种情况？一趟归并设i

指向待归并序列的第一个记录，归并的步长是2h情况1：i+2h≤n，则相邻两个有序子序列的长度均为hihhi+2hnwhile(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}算法描述：voidSort::Merge(intfirst1,intlast1,intlast2)子序列长度有什么规律？在一趟归并中有几种情况？情况2：i+h＜n，则相邻有序子序列一个长度为h，另一个长度小于hif(i+h<length)

Merge(i,i+h-1,length-1);算法描述：hii+hn<h一趟归并设i

指向待归并序列的第一个记录，归并的步长是2h子序列长度有什么规律？在一趟归并中有几种情况？voidSort::Merge(intfirst1,intlast1,intlast2)情况3：i

+h≥

n，则表明只剩下一个有序子序列算法实现voidSort::MergePass(inth){inti=0;while(i+2*h<=length){Merge(i,i+h-1,i+2*h-1);i=i+2*h;}if(i+h<length)

Merge(i,i+h-1,length-1);}如何控制二路归并的结束？子序列长度有什么规律？voidSort::MergeSort(){inth=1;while(h<length){MergePass(h);h=2*h;}}25204015202525154020154015202540时间性能执行趟数：log2n每一趟：将记录扫描一遍，O(n)最好、最坏、平均情况：O(nlog2n)二路归并执行多少趟？每一趟的时间性能是多少？空间性能：合并不能就地进行，O(n)稳定性：稳定如果将判断条件改为(r[i]<r[j])，仍然是稳定的吗？while(i<=m&&j<=t)if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];252040152025251540201540152025407-6外部排序v第七章排序技术学什么？外部排序的基本思想置换-选择排序败者树为什么外部排序需要新算法？外部排序需要着重考虑什么？基本思想外部排序的基本思想：采用多路归并排序，分为以下两个阶段：外部排序（externalsorting）：待排序的记录以文件的形式存储在外存上，在排序过程中需要在内存和外存之间进行多次数据交换预处理阶段：根据可用内存的大小，将原文件分解成多个能够一次性装入内存的子文件，分别对每一个子文件在内存中完成排序，得到若干个有序的子文件（称为归并段）；归并排序阶段：对归并段进行若干趟多路归并排序，直至将整个文件的记录排好序。为什么外部排序在归并排序阶段采用多路归并呢？R1R2R3R4R5R6R7R8R9R10R11R12归并段及归并结果不能同时存放在内存中，需要多次对外存进行读/写操作。基本思想R13R14R13R14R15R1R2R3R4R5R6R7R8R15多路归并可以减少归并排序的趟数对外存读/写操作的次数和归并排序的趟数成正比置换-选择排序假设待排序文件有

n个记录，内存缓冲区的容量是

k，每次将

k个记录读入内存进行排序，得到归并段的个数是多少？

如何增大归并段的记录个数呢？如何减少归并排序执行的趟数呢？采用多路归并

k-路归并排序

在k

个记录中取出最小值

败者树减少归并段的个数

增大归并段的记录个数增大k归并段的个数是n/k算法：置换-选择排序输入：待排序文件FI输出：归并段文件FO1.从文件FI中读取

w个记录到内存缓冲区buf；2.从buf中选取值最小的记录，记为

rmin；3.将

rmin输出到FO；4.若FI不空，则从FI中读取1个记录到buf中，转步骤5；否则，重复执行步骤2和步骤3，直至缓冲区buf为空，算法结束；5.从buf中所有比记录

rmin值大的记录中，选取值最小的记录，重新记为

rmin，转步骤3；6.如果buf中没有比记录

rmin值大的记录，则得到1个初始归并段，转步骤2构造下一个归并段；假设内存缓冲区buf可容纳

w个记录，假设每个物理块只能容纳1个记录置换-选择排序例1假设内存缓冲区buf可容纳4个记录，文件FI包含的记录为{10,20,12,18,6,25,5,22,15,30,28,10}，写出置换-选择排序的过程。归并段2615285归并段1内存缓冲区102012181528对于长度不等的初始归并段，不同的多路归并方案对排序性能有什么影响？620121810620251812186202552062225561525522615305256152853061528105152810615281028置换-选择排序最佳归并树例2置换-选择排序生成了9个初始归并段，长度分别为{9,30,12,18,3,17,2,6,24}，假设采用3-路归并排序。9301251183173826243212123611912321718245932121WPL=242WPL=223最佳归并树：带权路径长度最小的归并树。对于长度不等的初始归并段，不同的多路归并方案对排序性能有什么影响？方案1：方案2：最佳归并树需添加(k-1)-(n-1)mod(k-1)个虚段具有n个初始归并段，合并为k-路最佳归并树，需要填加多少个虚段？2311912321718245932121什么是虚段？长度为0的归并段败者树如何快速在多个记录中选取值最小的记录？顺序查找

k–1次比较败者树

O(log2k)败者树（treeofloser）：分支结点表示左、右孩子结点中的败者，让胜者去参加更高一层的比较。胜者树——小根堆：根结点为最小值121512101055205败者树：根结点的胜者为最小值15151210122052012121055败者树采用败者树进行5-路归并排序7-7各种排序方法的比较v第七章排序技术学什么？各种排序方法的使用范例各种排序方法的综合比较使用范例#include<iostream>#include<cmath>usingnamespacestd;//将排序类定义和各个排序算法的成员函数定义放到这里

intmain(){intselect,r[10]={2,5,1,7,9,4,3,6,5,8};SortL{r,10};cout<<"1.直接插入排序2.希尔排序"<<endl;cout<<"3.