北邮数据结构排序课件

第八章排序北京邮电大学信息与通信工程学院《数据结构与STL》第八章排序北京邮电大学《数据结构与STL》第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/1421.概述《数据结构与STL》第八章排序学习内容：2023/8/421.概述《数据结构1概述排序给定一个记录序列，按照每个记录的关键码将记录进行重新排列，使关键码从小到大/从大到小有序。正序：关键码从小到大排列逆序：关键码从大到小排列2023/8/143《数据结构与STL》1概述排序2023/8/43《数据结构与STL》1概述趟在排序算法中，将待排序的记录扫描一遍称为一趟。稳定性待排序记录中具有相同关键码的记录，若排序前后，这些记录的相对位置不变，则为稳定排序；否则为不稳定。2023/8/144《数据结构与STL》1概述趟2023/8/44《数据结构与STL》1概述排序的分类

根据是否将全部记录放进内存，分为内部排序和外部排序

根据排序的原则，可以将排序分成：

插入排序交换排序

选择排序

归并排序2023/8/145《数据结构与STL》1概述排序的分类2023/8/45《数据结构与STL》1概述如何评价一个排序算法？排序的基本操作:比较和移动主要:比较的次数或移动次数较少的算法性能较好。次要:空间复杂度.算法本身的复杂度2023/8/146《数据结构与STL》1概述如何评价一个排序算法？2023/8/46《数据结构与第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/1472.插入排序《数据结构与STL》第八章排序学习内容：2023/8/472.插入排序《数据插入排序主要内容1．存储结构2．直接插入排序3．希尔排序2023/8/148《数据结构与STL》插入排序主要内容2023/8/48《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];2023/8/149《数据结构与STL》1．存储结构排序使用顺序结构2023/8/49《数据结构与S2.插入排序插入排序的特征类似于玩纸牌时整理手中纸牌的过程。寻找一个指定记录在待排序记录中的位置，然后插入的排序算法。2023/8/1410《数据结构与STL》2.插入排序插入排序的特征2023/8/410《数据结构与2.直接插入排序基本思想

每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录排序好。2023/8/1411《数据结构与STL》r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置2.直接插入排序基本思想2023/8/411《数据结构与ST2.直接插入排序需要解决的问题1）如何构造初始有序序列？2）如何找到插入的位置？2023/8/1412《数据结构与STL》r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置2.直接插入排序需要解决的问题2023/8/412《数据结构1）如何构造初始有序序列？2023/8/1413有序序列r[1]无序序列r[3..n]r[2]第一趟有序序列r[1..2]无序序列r[4..n]r[3]第二趟第n-1趟有序序列r[1..n-1]r[n]……《数据结构与STL》1）如何构造初始有序序列？2023/8/413有序序直接插入排序的过程2023/8/1414初始序列[12一趟[1215]920103124第二趟[91215]20103124第三趟[9121520]103124第四趟[910121520]3124第五趟[910121520

31]24第六趟[9101215202431]《数据结构与STL》直接插入排序的过程2023/8/414初始序列[12]152）如何找到插入的位置？基本思想设置r[0]为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r[0]插入。

2023/8/1415r1≤r2≤……≤ri-1|riri+1……rn有序区无序区插入到合适的位置r[0]=r[i];for(intj=i-1;r[0]<r[j];j--)r[j+1]=r[j];r[j+1]=r[0];《数据结构与STL》if

(r[i]<r[i-1]){

r[0]=r[i];

for(intj=i-1;r[0]<r[j];j--)

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

r[j+1]=r[0];}2）如何找到插入的位置？基本思想2023/8/415r1≤r2.直接插入排序的算法voidInsertSort(intr[],intn)//升序排列{for(inti=2;i<=n;i++)//i从2~n循环，共n-1趟排序{r[0]=r[i];for(intj=i-1;r[0]<r[j];j--)r[j+1]=r[j];r[j+1]=r[0];}}2023/8/1416《数据结构与STL》2.直接插入排序的算法voidInsertSort(in2.直接插入排序的性能分析最好情况正序序列：比较

移动最坏情况逆序序列：比较

移动平均情况时间复杂度O(n2)空间复杂度O(1)

2023/8/14《数据结构与STL》17

n-102.直接插入排序的性能分析最好情况2023/8/4《数据结2.直接插入排序的特点稳定性插入排序是一种稳定的排序算法适用性尤其适合待排序记录基本有序的情况2023/8/1418《数据结构与STL》2.直接插入排序的特点稳定性2023/8/418《数据结构3.希尔排序希尔排序是对插入排序的一种改进,原因1)基本有序的序列，直接插入最快2)无序序列，记录数很少时，也很快基本思想将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。2023/8/1419《数据结构与STL》3.希尔排序希尔排序是对插入排序的一种改进,原因2023/3.希尔排序2023/8/1420《数据结构与STL》49386597761327495504原始序列d=10/2=513274955044938659776第一趟d=5/2=23.希尔排序2023/8/420《数据结构与STL》493.希尔排序2023/8/1421《数据结构与STL》04271349385549659776第二趟d=2/2=104132738494955657697第三趟3.希尔排序2023/8/421《数据结构与STL》043.希尔排序（缩小增量排序）具体排序过程设待排序对象序列有n个记录,先取d<n，比如d=n/2作为间隔,将全部对象分为d个子序列,对每一个子序列中分别施行直接插入排序。然后缩小间隔d,例如取d=d/2，重复上述的子序列划分和排序工作。直到最后取d=1,将所有对象放在同一个序列中排序为止。2023/8/1422《数据结构与STL》3.希尔排序（缩小增量排序）具体排序过程2023/8/4223.希尔排序希尔排序的子序列划分for(intd=n/2;d>=1;d=d/2)//以d为增量{

以d为增量，在子序列中进行插入排序。}2023/8/1423《数据结构与STL》3.希尔排序希尔排序的子序列划分2023/8/423《数据结希尔排序假设增量=d，则一趟希尔排序的过程for(inti=d+1;i<=n;i++)//一趟希尔排序{ if(r[i]<r[i-d]) { r[0]=r[i]; for(intj=i-d;j>0&&r[0]<r[j];j=j-d) r[j+d]=r[j]; r[j+d]=r[0]; }}2023/8/1424《数据结构与STL》希尔排序假设增量=d，则一趟希尔排序的过程2023/8/422023/8/14《数据结构与STL》2513 38 5576132749

55

044938659776

04 2765494997假设增量=3，则一趟希尔排序的过程2023/8/4《数据结构与STL》2513 383.希尔排序voidShellInsert(intr[],intn){ for(intd=n/2;d>=1;d=d/2)//以d为增量 { for(inti=d+1;i<=n;i++)//一趟希尔排序 { if(r[i]<r[i-d]) { r[0]=r[i]; for(intj=i-d;j>0&&r[0]<r[j];j=j-d) r[j+d]=r[j]; r[j+d]=r[0]; } } }}2023/8/1426《数据结构与STL》3.希尔排序voidShellInsert(intr3.希尔排序的性能分析时间复杂度希尔排序的时间与“增量序列”有关，不同的“增量序列”时间复杂度不同。经过大量的实验，时间复杂度O(n2)和O(nlog2n)之间稳定性希尔排序是一种不稳定的排序算法2023/8/1427《数据结构与STL》3.希尔排序的性能分析时间复杂度2023/8/427《数据结第八章排序学习内容： 1.概述

2.插入排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/14283.交换排序《数据结构与STL》第八章排序学习内容：2023/8/4283.交换排序《数交换排序主要内容1．存储结构2．起泡排序3．起泡排序（改进）4．快速排序5．快速排序（改进）2023/8/1429《数据结构与STL》交换排序主要内容2023/8/429《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];交换排序的特征在待排序的记录中选择两个记录，将它们的关键码进行比较，如果反序则交换它们的位置。2023/8/1430《数据结构与STL》1．存储结构排序使用顺序结构2023/8/430《数据结构与2.起泡排序基本思想

两两比较相邻的记录,如果反序,则交换位置,直到没有反序的记录为止。2023/8/1431无序序列r[1..i]有序序列r[i+1..n]反序则交换标记《数据结构与STL》2.起泡排序基本思想2023/8/431无序序列r[1..起泡排序的过程2023/8/1432第一趟初始状态《数据结构与STL》起泡排序的过程2023/8/432第一趟初始状态《数据结构与第二趟无序区有序区无序区有序区2023/8/1433《数据结构与STL》第二趟无序区有序区无序区有序区2023/8/433《数据结构2.起泡排序voidBubbleSort(intr[],intn){ //外循环：总共需要遍历的趟数

for(inti=1;i<n;i++)//n-1趟

{ //内循环：每一趟需要比较的次数

for(intj

=

1;j

<=

n-i;

j++) { if(r[j]>r[j+1])//相邻元素比较

{ r[0]=r[j]; r[j]=r[j+1]; r[j+1]=r[0]; } } }}2023/8/1434《数据结构与STL》2.起泡排序voidBubbleSort(intr[3.起泡排序（改进）2023/8/14《数据结构与STL》35初始序列[5013559727384965]第一趟[13

5055972738

4965][13

5055279738

4965][13

5055273897

4965][13

50552738499765][13

505527384965]97pos第二趟[13

502755384965]97[13

502738554965]97[13

50273849]556597pospos=n3.起泡排序（改进）2023/8/4《数据结构与STL》33.起泡排序（改进）2023/8/14《数据结构与STL》36第三趟[1327503849

]

556597[132738

5049

]

556597[13273849

]50

556597pos第四趟[13273849

]50

556597pos3.起泡排序（改进）2023/8/4《数据结构与STL》33.起泡排序（改进）具体过程1）初始状态无序区为r[1..n]2）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置pos。最后一次交换的位置pos，就是下一趟无序区r[1..pos]3）反复执行2），直到无序区中没有反序的记录2023/8/1437《数据结构与STL》3.起泡排序（改进）具体过程2023/8/437《数据结构3.起泡排序（改进）已知无序区r[1..pos]，则如何进行反序交换?intbound=pos;//带排序记录右边界pos=0;//标记，记录交换的位置 for(inti=1;i<bound;i++) { if(r[i]>r[i+1]) { r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0]; pos=i;//记录最后交换的位置 } }2023/8/1438《数据结构与STL》3.起泡排序（改进）已知无序区r[1..pos]，则如何进3.起泡排序（改进）voidBubbleSort(intr[],intn){ intpos=n; while(pos!=0) { intbound=pos;//本次无序记录的范围 pos=0; for(inti=1;i<bound;i++) if(r[i]>r[i+1])//相邻记录比较 { r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];//交换 pos=i; } }}2023/8/1439《数据结构与STL》3.起泡排序（改进）voidBubbleSort(i3.起泡排序的性能分析2023/8/1440《数据结构与STL》最好情况正序序列：比较

移动最坏情况逆序序列：比较

移动平均情况时间复杂度O(n2)空间复杂度O(1)n-103.起泡排序的性能分析2023/8/440《数据结构与STL4.快速排序快速排序是起泡排序的改进改进着眼点起泡排序：记录的比较和移动是在相邻位置进行，需要比较移动多次才能到最终的位置。

快速排序：记录的比较和移动从两端向中间进行的，记录移动的距离较远。2023/8/1441《数据结构与STL》4.快速排序快速排序是起泡排序的改进2023/8/441《数4.快速排序快速排序又叫分区交换排序，其基本思想：1.选择一个记录作为轴值，将记录分成2部分。2.分别对这两部分重复上述过程。2023/8/1442《数据结构与STL》[r1r2……ri-1]

ri[ri+1ri+2……rn

]全部<=ri轴值全部>=ri递归4.快速排序快速排序又叫分区交换排序，其基本思想：2023/4.快速排序需要解决的问题1.如何选择基准记录？记录集中的第一个记录。2.如何分区，使大于基准的记录后移，小于基准的记录前移？3.如何判决快速排序结束？递归缩小分区，直到分区只有一个记录。2023/8/1443[r1r2……ri-1]

ri[ri+1ri+2……rn

]全部<=ri轴值全部>=ri《数据结构与STL》4.快速排序需要解决的问题2023/8/443[r1r2…2.如何分区？分区算法①初始化取第一个记录R[1]作为基准i基准左侧待比较的记录，初始i=1j基准右侧待比较的记录,初始j=n②右侧扫描从后向前找到第一个比基准小的记录，和基准交换③左侧扫描从前到后找到第一个比基准大的记录，和基准交换

反复执行②③，直到i=j结束2023/8/1444《数据结构与STL》2.如何分区？分区算法2023/8/444《数据结构与ST2.如何分区？2023/8/144521254925*1608012345pivotji25*251649082125*251649082125*2516082149《数据结构与STL》2.如何分区？2023/8/44521254925*1602.如何分区？2023/8/14464925*25160821一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。2125*25164908《数据结构与STL》2.如何分区？2023/8/4464925*2516082一趟快速排序intPartion(intr[],inti,intj){ intpivot=r[i]; while(i<j) { while((i<j)&&(r[j]>=pivot)) j--; r[j]

r[i]; while((i<j)&&(r[i]<=pivot)) i++; r[j]

r[i]; } returni;}2023/8/1447《数据结构与STL》一趟快速排序intPartion(intr[],int5．快速排序（改进）改进出发点一趟快速排序：每交换一对记录需要进行三次移动，而实际上排序过程中对pivot的位置交换是多余的，只有i=j的位置才是pivot的位置。所以，可以将pivot保存在r[0]中，排序过程中只有r[i]和r[j]移动。2023/8/1448《数据结构与STL》5．快速排序（改进）改进出发点2023/8/448《数据结构2）分区改进分区算法①初始化取第一个记录作为基准，保存在任意位置i基准左侧待比较的记录，初始i=1j基准右侧待比较的记录,初始j=n②右侧扫描从后向前找到第一个比基准小的记录，移至位置i③左侧扫描从前到后找到第一个比基准大的记录，移至位置j

反复执行②③，直到i=j结束，将r[0]移至r[i]。

2023/8/1449《数据结构与STL》2）分区改进分区算法2023/8/449《数据结构与STL》21254925*16080

1

2

3

4

5

6pivot25*2516490821ji25*251649082125*25164908214925*25160821212023/8/1450《数据结构与STL》21254925*1608015．快速排序（改进）2023/8/14512125*25164908一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。《数据结构与STL》5．快速排序（改进）2023/8/4512125*25164一趟快速排序（改进）intPartion(intr[],intfirst,intend){ inti=first;intj=end;intpivot=r[i];//选取基准记录 while(i<j) { while((i<j)&&(r[j]>=pivot))//右侧扫描 j--; r[i

++]=r[j]; while((i<j)&&(r[i]<=pivot))//左侧扫描 i++; r[j--]=r[i]; } r[i]=pivot； returni;}2023/8/1452《数据结构与STL》一趟快速排序（改进）intPartion(intr[]5．快速排序（改进）2023/8/1453pivot2125*25164908pivot第一趟25*1608254921pivot第二趟4908162525*21第三趟《数据结构与STL》5．快速排序（改进）2023/8/453pivot2125*5.快速排序voidQsort(intr[],inti,intj){ if(i<j) { intpivotloc=Partion(r,i,j); Qsort(r,i,pivotloc-1); Qsort(r,pivotloc+1,j); }}2023/8/1454《数据结构与STL》5.快速排序voidQsort(intr[],int5.快速排序的性能分析最好情况每次划分的左侧序列和右侧序列的长度相同。表长为n的序列可划分log2n层。定位一个记录要对整个待划分序列扫描一遍，所需时间O(n)。

总的时间复杂度O(nlog2n)。2023/8/1455n/4n/4n/4n/4n/2n/2n

《数据结构与STL》5.快速排序的性能分析最好情况2023/8/455n/4n/5.快速排序的性能分析2023/8/1456《数据结构与STL》最坏情况待排序记录为逆序或正序，每次划分只得到比上一次少一个的子序列，此时必须要n-1次递归，第i次需要n-i次比较，所以，总的比较次数：记录的移动次数<=比较次数，所以总的时间复杂度O(n2)5.快速排序的性能分析2023/8/456《数据结构与STL5.快速排序的性能分析平均性能时间复杂度O(nlog2n)栈的深度O(log2n)特点快速排序是一种不稳定的排序方法2023/8/1457《数据结构与STL》5.快速排序的性能分析平均性能2023/8/457《数据结构第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序 5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/14584.选择排序《数据结构与STL》第八章排序学习内容：2023/8/4584.选择排序《数选择排序主要内容1．存储结构2．简单选择排序3．堆排序2023/8/1459《数据结构与STL》选择排序主要内容2023/8/459《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n+1];r[1],r[2],…,r[n]选择排序的特征每趟排序在待排序序列中选择关键码最小的记录，添加到有序序列中。2023/8/1460《数据结构与STL》1．存储结构排序使用顺序结构2023/8/460《数据结构与2.简单选择排序基本思想第i趟排序在无序序列r[i..n]中选择关键码最小的记录，与r[i]交换，使有序序列不断增长直到全部排序完毕。2023/8/1461r1≤r2≤……≤ri-1|riri+1…rmin…rn有序区无序区交换《数据结构与STL》2.简单选择排序基本思想2023/8/461r1≤r2≤2.简单选择排序2023/8/146249276597761338初始化

13

276597764938第一趟13276597764938第二趟如何在r[i..n]中选择最小的记录？13273897764965第三趟13273849769765第四趟13273849659776第五趟13273849657697第六趟《数据结构与STL》2.简单选择排序2023/8/4624927652.简单选择排序1）如何在无序区r[i..n]选择最小的记录?假设无序区的r[i]是最小记录，附设一个变量index=i,然后依次将后续的记录与r[index]比较，如果比r[index]小，则index记录该位置。 int

index=i;//假设index是最小的 for(int

j=i+1;j<=n;j++)

//选择最小记录的位置 if(r[j]<r[index]) index=j

2)比较完毕，交换r[index]和r[i]的记录。2023/8/1463index记录无序区最小记录的位置《数据结构与STL》2.简单选择排序1）如何在无序区r[i..n]选择最小的记录2.简单选择排序voidSelectSort(intr[],intn){ for(inti=1;i<n;i++)//n-1趟排序

{ intindex=i; //假设index是最小的

for(intj=i+1;j<=n;j++) //查找最小记录的位置

if(r[j]<r[index]) index=j; if(index!=i) //若第一个就是最小元素，则不用交换

{ r[0]=r[i]; r[i]=r[index]; r[index]=r[0]; //利用r[0]作为临时空间交换记录

} }}2023/8/1464《数据结构与STL》2.简单选择排序voidSelectSort(intr[2.简单选择排序性能分析特点移动次数最少，稳定的排序算法最好情况正序序列：比较 移动最坏情况序列：比较 移动逆序序列-不是最坏移动平均情况时间复杂度 O(n2) 空间复杂度O(1)2023/8/14《数据结构与STL》6503*(n-1)3*(n-1)/22.简单选择排序性能分析特点2023/8/4《数据结构与ST3.堆排序什么是堆？堆是具有下列性质的完全二叉树：小根堆：每个结点的值≤左右孩子结点的值大根堆：每个结点的值≥左右孩子结点的值

ki

≤k2iki

≥k2iki

≤k2i+1

或ki

≥k2i+1

2023/8/1466小根堆大根堆《数据结构与STL》3.堆排序什么是堆？2023/8/466小根堆大根堆《数据3.堆排序小根堆大根堆2023/8/1467101556253070705630251510(10,15,56,25,30,70)(70,56,30,25,15,10)

堆的特点：根结点一定是最大或最小者《数据结构与STL》3.堆排序小根堆大根堆2023/8/46710155625思考？

{12,36,27,65,40,14,98,81}这个序列是不是堆？2023/8/14681236276540149881《数据结构与STL》思考？{12,36,27,65,40,14,93.堆排序堆调整问题一棵完全二叉树中，根结点的左右子树都是堆，如何调整根结点，使整棵二叉树成为一个堆？2023/8/14694024453276654997《数据结构与STL》3.堆排序堆调整问题2023/8/469402445327堆调整过程——筛选小根堆筛选：总是将根结点与左右孩子进行比较，若不满足堆的条件，则将根结点与较小的结点交换，一直到叶子结点，或所有子树均为堆为止。2023/8/1470402445327665499740243240《数据结构与STL》堆调整过程——筛选小根堆筛选：2023/8/47040244筛选算法堆的存储结构顺序存储结构，r[i]是r[2i]r[2i+1]的父结点前提

1）要筛选的结点编号是k

2）堆中最后一个结点的编号是m

3）结点k的左右子树均为堆（即r[k+1]~r[m]满足堆的条件）2023/8/1471《数据结构与STL》筛选算法堆的存储结构2023/8/471《数据结构与STL》筛选算法(小根堆)voidSift(intr[],intk,intm){ inti=k，j=2*i;//i是要筛选的结点，j是i的左孩子 while(j<=m) { if(j<m&&r[j]>r[j+1])j++;//j是左右孩子中较小者 if(r[i]<r[j])break;//符合小根堆的条件，结束 else { r[i]

r[j];//根结点与孩子结点交换 i=j;j=2*i; } }}2023/8/1472《数据结构与STL》筛选算法(小根堆)voidSift(intr[],i4.堆排序什么是堆排序？1）将待排序的记录构造成一个堆2）输出堆顶元素3）将堆中最后一个元素移至堆顶，并将剩余元素调整成堆。反复执行2)3)，直到堆中只有一个记录。2023/8/1473《数据结构与STL》4.堆排序什么是堆排序？2023/8/473《数据结构与S4.堆排序将待排序的记录构造成一个堆？前提完全二叉树使用顺序序列存储步骤1）所有叶子结点都是堆2）从n/2个记录(最后一个分支结点)开始筛选3）直到根结点，结束2023/8/1474《数据结构与STL》4.堆排序将待排序的记录构造成一个堆？2023/8/4744.堆排序——建堆（小根堆）for(int

i=n/2;i>=1;i--)Sift(r,i,n);2023/8/14754938659776132749493865977613274949976513134913382749766549974927《数据结构与STL》4.堆排序——建堆（小根堆）for(inti=n/4.堆排序如何输出堆顶元素？将堆顶元素和最后一个元素交换如何将剩余元素调整成堆？

1)需要输出堆顶元素n-1次

2)则第i次，需要调整的元素范围r[1..n-i]2023/8/1476《数据结构与STL》4.堆排序如何输出堆顶元素？2023/8/476《数据结构4.堆排序——筛选（小根堆）r[1]r[n];Sift(r,1,n-1);2023/8/1477133827497665499713972797499713382749766549972738494976659713输出堆顶元素《数据结构与STL》4.堆排序——筛选（小根堆）r[1]r[n];204.堆排序——筛选（小根堆）r[1]r[n-1];Sift(r,1,n-2);2023/8/1478273849497665971397279749382738494976659713输出堆顶元素384949977665271397《数据结构与STL》4.堆排序——筛选（小根堆）r[1]r[n-1];4.堆排序——筛选（小根堆）r[1]r[n-2];Sift(r,1,n-3);2023/8/1479输出堆顶元素3849499776652713384949977665971327653849654965499776382713《数据结构与STL》4.堆排序——筛选（小根堆）r[1]r[n-2];4.堆排序——筛选（小根堆）r[1]r[n-i+1];Sift(r,1,n-i);2023/8/14804965499776971327384965499776382713输出堆顶元素《数据结构与STL》4.堆排序——筛选（小根堆）r[1]r[n-i+14.堆排序——算法voidSift(intr[],intk,intm){inti=k，j=2*i;//i是要筛选的结点，j是i的左孩子

while(j<=m){if(j<m&&r[j]>r[j+1])j++;//j是左右孩子中较小者

if(r[i]<r[j])break;//符合小根堆的条件，结束

else{r[i]<->r[j]; //根结点与孩子结点交换

i=j;j=2*i;}}}2023/8/1481《数据结构与STL》4.堆排序——算法voidSift(intr[],4.堆排序性能分析堆排序的时间消耗1.建堆时间复杂度O(nlog2n)2.重建堆时的筛选第i次输出堆顶记录重建堆的时间为O(log2(n-i))，需要n-1次输出堆顶元素。总的是间复杂度O(nlog2n)堆排序是一种不稳定的排序方法。2023/8/1482《数据结构与STL》4.堆排序性能分析堆排序的时间消耗2023/8/482《数第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/14835.归并排序《数据结构与STL》第八章排序学习内容：2023/8/4835.归并排序《数归并排序主要内容1．存储结构2．二路归并排序（非递归）

3．二路归并排序（递归）2023/8/1484《数据结构与STL》归并排序主要内容2023/8/484《数据结构与STL》1．存储结构排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。intr[n];归并排序的特征将两个或两个以上的有序序列归并成一个有序序列的过程。2023/8/1485《数据结构与STL》1．存储结构排序使用顺序结构2023/8/485《数据结构与归并排序最简单的归并排序——两路归并排序1）将n个记录的序列分成n个子集

2）将相邻的两个子合并成n/2个子集3）将相邻的两个子合并成n/4个子集……合并成一个子集。2023/8/1486《数据结构与STL》归并排序最简单的归并排序——两路归并排序2023/8/4862.二路归并排序初始序列

(49)(38)(65)(97)(76)(13)(27)2023/8/1487(3849)

(6597)(1376)27(38496597)

(132776)(13273849657697)一趟二趟三趟《数据结构与STL》2.二路归并排序初始序列2023/8/487(382.二路归并排序1.如何构造初始序列？将整个序列看成是长度为1的n个有序序列2.如何将相邻序列归并在一起？相邻序列r[s]~r[m]和r[m+1]~r[t]，归并成一个新序列r1[s]~r1[t]。

2023/8/1488r[m+1]~r[t]，r[s]~r[m]，r1[s]~r1[t]，有序序列有序序列

《数据结构与STL》2.二路归并排序1.如何构造初始序列？2023/8/488r归并一次voidMerge(intr[],intr1[],ints,intm,intt){inti=s;//i指向r[s~m]intj=m+1;//j指向r[m+1~t],intk=s;//k指向r1;while(i<=m&&j<=t) {if(r[i]<r[j]) r1[k++]=r[i++];//取r[i]和r[j]中较小者放入r1[k]，并且自加1else r1[k++]=r[j++];}2023/8/1489r[m+1]~r[t]，r[s]~r[m]，r1[s]~r1[t]，有序序列有序序列《数据结构与STL》归并一次voidMerge(intr[],intr归并一次if(i<=m)//若r[s~m]没处理完

while(i<=m)r1[k++]=r[i++];if(j<=t)//若r[m+1~t]没处理完

while(j<=t)r1[k++]=r[j++];}2023/8/1490r[m+1]~r[t]，r[s]~r[m]，r1[s]~r1[t]，有序序列有序序列《数据结构与STL》归并一次if(i<=m)//若r[s~m]没处理完202.一趟归并（非递归）1.分析除最后一个序列外，其他序列的长度相同，用h表示把若干个长度为h的序列和最后一个<=h的序列两两归并，把结果保存在r1[1..n]中2023/8/1491hhhh1nii《数据结构与STL》2.一趟归并（非递归）1.分析2023/8/491hhhh2.一趟归并（非递归）三种情况

2023/8/1492hhhh1nii<=hi>n-h+1hhhh1nii<hi<n-h+1hhhhh1niii<=n-2h+1《数据结构与STL》2.一趟归并（非递归）三种情况2023/8/492hhhh12.一趟归并的算法（非递归）voidMergePass(intr[],intr1[],intn,inth){inti=1;while(i<=n-2*h+1)//长度为h的序列两两归并

{Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;}if(i<n-h+1)Merge(r,r1,i,i+h-1,n);//两个序列，其中一个<helsefor(;i<=n;i++)//只有一个<=h的序列

r1[i]=r[i];}2023/8/1493《数据结构与STL》2.一趟归并的算法（非递归）voidMergePass(i2.归并排序的算法（非递归）voidMergeSort(intr[],intr1[],intn){inth=1;while(h<n){MergePass(r,r1,n,h);h=2*h;for(inti=1;i<=n;i++) r[i]=r1[i];}}2023/8/1494《数据结构与STL》2.归并排序的算法（非递归）voidMergeSort(i3.归并算法——递归2023/8/14954938659776132749386597761327493865977613274938659713763849659738496597271376271327761327384965

76

97《数据结构与STL》3.归并算法——递归2023/8/4954938651.归并voidMergeSort(intr[],intr1[],ints,intt){intr2[MAXSIZE];if(s==t)r1[s]=r[s];else{intm=(s+t)/2;//将r平分成r[s..m]和r[m+1..t]MergeSort(r,r1,s,m);//递归的将r[s..m]归并为r1[s..m]MergeSort(r,r1,m+1,t); //递归的将r[m+1..t]归并为r1[m+1..t]Merge(r1,r,s,m,t);//将r1[s..m]和r1[m+1..t]归并r[s..t]}}voidmain()//主函数中调用如下：{ intr[12]={5,3,7,2,9,10,12,4,30,8,1,6},intr1[12];MergeSort(r,r1,0,11);}2023/8/1496《数据结构与STL》1.归并voidMergeSort(intr[],3．归并排序的性能分析时间性能归并排序需要log2n趟，每趟需要把结果存在r[1~n]中，需要O(n)时间复杂度O(nlog2n)空间性能

空间复杂度O(n)归并排序是稳定的排序方法2023/8/1497《数据结构与STL》3．归并排序的性能分析时间性能2023/8/497《数据结构第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/14986.排序比较《数据结构与STL》第八章排序学习内容：2023/8/4986.排序比较《数各种排序的比较排序方法平均情况最好情况最坏情况辅助空间直接插入O(n2)O(n)O(n2)O(1)希尔排序O(nlog2n)~O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)简单选择O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)2023/8/1499《数据结构与STL》各种排序的比较排序方法平均情况最好情况最坏情况辅助空间直接插比较时间性能1.快速排序：平均性能最好2.待排序序列较多：归并排序快于堆排序

时间性能

2023/8/14100《数据结构与STL》比较时间性能2023/8/4100《数据结构与STL》比较稳定的排序：直接插入排序.起泡排序.简单选择排序.

归并排序不稳定的排序希尔排序.快速排序.堆排序2023/8/14101《数据结构与STL》比较稳定的排序：2023/8/4101《数据结构与STL》第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/141027.外部排序《数据结构与STL》第八章排序学习内容：2023/8/41027.外部排序《7.外部排序定义内部排序若整个排序过程中不涉及数据的内、外存交换，待排序的记录全部存放在内存中排序，称为内部排序。外部排序若待排序的的文件很大，就无法将整个文件的所有记录同时调入内存进行排序，只能将文件放在外存上，我们称这种排序为外部排序。2023/8/14103《数据结构与STL》7.外部排序定义2023/8/4103《数据结构与STL》7.外部排序基本思想内外存交换和“内部归并”主要步骤：1将待排序记录分成若干长度为t的段R1、R2、……、Rn，t的长度应该足够长但不能超过可用来排序的内存空间；2利用上述内部排序方法，对每一段进行内部排序，这些经过排序的段通常称为“顺串”，“顺串”生成后即写入外存；3对这些“顺串”进行归并，使“顺串”的长度逐渐增大，直至待排序的记录成为一个顺串。2023/8/14104《数据结构与STL》7.外部排序基本思想2023/8/4104《数据结构与ST第八章排序学习内容： 1.概述

2.插入排序

3.交换排序

4.选择排序

5.归并排序 6.排序比较

7.外部排序 8.STL中相关排序算法2023/8/141058.STL中相关排序算法《数据结构与STL》第八章排序学习内容：2023/8/41058.STL中8.STL中相关排序算法STLsort算法函数包括：2023/8/14106《数据结构与STL》函数名功能描述sort对给定区间所有元素进行排序stable_sort对给定区间所有元素进行稳定排序partial_sort对给定区间所有元素部分排序partial_sort_copy对给定区间复制并排序nth_element找出给定区间的某个位置对应的元素is_sorted判断一个区间是否已经排好序partition使得符合某个条件的元素放在