北邮数据结构排序ppt课件.ppt

第八章 排序,北京邮电大学信息与通信工程学院,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,2,1. 概述,数据结构与STL,1 概述,排序 给定一个记录序列，按照每个记录的关键码将记录进行重新排列，使关键码从小到大/从大到小有序。正序：关键码从小到大排列逆序：关键码从大到小排列,2022/12/25,3,数据结构与STL,1 概述,趟 在排序算法中，将待排序的记录扫描一遍称为一趟。稳定性 待排序记录中具有相同关键码的记录，若排序前后，这些记录的相对位置不变，则为稳定排序；否则为不稳定。,2022/12/25,4,数据结构与STL,1 概述,排序的分类 根据是否将全部记录放进内存，分为内部排序和外部排序 根据排序的原则，可以将排序分成： 插入排序 交换排序 选择排序 归并排序,2022/12/25,5,数据结构与STL,1 概述,如何评价一个排序算法？排序的基本操作:比较和移动主要:比较的次数或移动次数较少的算法性能较好。次要:空间复杂度. 算法本身的复杂度,2022/12/25,6,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,7,2. 插入排序,数据结构与STL,插入排序,主要内容1存储结构2直接插入排序3希尔排序,2022/12/25,8,数据结构与STL,1存储结构,排序使用顺序结构 为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。 int rn;,2022/12/25,9,数据结构与STL,2. 插入排序,插入排序的特征类似于玩纸牌时整理手中纸牌的过程。寻找一个指定记录在待排序记录中的位置，然后插入的排序算法。,2022/12/25,10,数据结构与STL,2.直接插入排序,基本思想 每次将一个待排序的记录按其关键码的大小插入到一个已经排序好的有序序列中，直到全部记录排序好。,2022/12/25,11,数据结构与STL,2.直接插入排序,需要解决的问题 1）如何构造初始有序序列？ 2）如何找到插入的位置？,2022/12/25,12,数据结构与STL,1）如何构造初始有序序列？,2022/12/25,13,数据结构与STL,直接插入排序的过程,2022/12/25,14,数据结构与STL,2）如何找到插入的位置？,基本思想 设置r0为“哨兵”，从后向前查找有序区，边查找边后移，直到找到合适的位置，将r0插入。,2022/12/25,15,r0=ri;for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0;,数据结构与STL,if (riri-1) r0=ri; for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0;,2. 直接插入排序的算法,void InsertSort(int r, int n) /升序排列 for (int i=2; i=n; i+) /i从2n循环，共n-1趟排序r0=ri; for (int j=i-1; r0rj; j-) rj+1 =rj; rj+1 = r0; ,2022/12/25,16,数据结构与STL,2. 直接插入排序的性能分析,最好情况正序序列：比较 移动最坏情况逆序序列：比较 移动平均情况时间复杂度O(n2) 空间复杂度O(1),2022/12/25,数据结构与STL,17,n-1,0,2. 直接插入排序的特点,稳定性插入排序是一种稳定的排序算法适用性 尤其适合待排序记录基本有序的情况,2022/12/25,18,数据结构与STL,3. 希尔排序,希尔排序是对插入排序的一种改进,原因1)基本有序的序列，直接插入最快2)无序序列，记录数很少时，也很快基本思想 将待排序的记录集分成多个子集，分别对这些子集进行排序，待整个序列基本有序时，在对记录进行一次直接插入排序。,2022/12/25,19,数据结构与STL,3.希尔排序,2022/12/25,20,数据结构与STL,49 38 65 97 76 13 27 49 55 04,原始序列 d=10/2=5,13 27 49 55 04 49 38 65 97 76,第一趟 d=5/2=2,3.希尔排序,2022/12/25,21,数据结构与STL,04 27 13 49 38 55 49 65 97 76,第二趟 d=2/2=1,04 13 27 38 49 49 55 65 76 97,第三趟,3.希尔排序（缩小增量排序）,具体排序过程设待排序对象序列有 n 个记录,先取 d n，比如d= n/2 作为间隔, 将全部对象分为 d 个子序列, 对每一个子序列中分别施行直接插入排序。然后缩小间隔 d, 例如取 d =d/2，重复上述的子序列划分和排序工作。直到最后取 d = 1, 将所有对象放在同一个序列中排序为止。,2022/12/25,22,数据结构与STL,3.希尔排序,希尔排序的子序列划分 for(int d=n/2; d=1;d=d/2) /以d为增量 以d为增量，在子序列中进行插入排序。,2022/12/25,23,数据结构与STL,希尔排序,假设增量=d，则一趟希尔排序的过程for (int i=d+1 ;i0 ,2022/12/25,24,数据结构与STL,2022/12/25,数据结构与STL,25,13 38 55 76,13 27 4955 04 49 38 65 97 76,04 27 65,49 49 97,假设增量=3，则一趟希尔排序的过程,3.希尔排序,void ShellInsert ( int r, int n) for(int d=n/2; d=1;d=d/2) /以d为增量 for (int i=d+1 ;i0 ,2022/12/25,26,数据结构与STL,3.希尔排序的性能分析,时间复杂度希尔排序的时间与“增量序列”有关，不同的“增量序列”时间复杂度不同。经过大量的实验，时间复杂度O(n2) 和 O(nlog2n) 之间稳定性 希尔排序是一种不稳定的排序算法,2022/12/25,27,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,28,3. 交换排序,数据结构与STL,交换排序,主要内容 1存储结构 2起泡排序 3起泡排序（改进） 4快速排序 5快速排序（改进）,2022/12/25,29,数据结构与STL,1存储结构,排序使用顺序结构 为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。 int rn;交换排序的特征 在待排序的记录中选择两个记录，将它们的关键码进行比较，如果反序则交换它们的位置。,2022/12/25,30,数据结构与STL,2. 起泡排序,基本思想 两两比较相邻的记录,如果反序,则交换位置,直到没有反序的记录为止。,2022/12/25,31,无序序列r1.i,有序序列 ri+1.n,反序则交换,标记,数据结构与STL,起泡排序的过程,2022/12/25,32,第一趟,初始状态,数据结构与STL,第二趟,无序区,有序区,2022/12/25,33,数据结构与STL,2. 起泡排序,void BubbleSort( int r, int n) /外循环：总共需要遍历的趟数 for (int i=1;irj+1) /相邻元素比较 r0=rj; rj = rj+1; rj+1 = r0; ,2022/12/25,34,数据结构与STL,3. 起泡排序（改进）,2022/12/25,数据结构与STL,35,初始序列,50 13 55 97 27 38 49 65,第一趟,13 50 55 97 27 38 49 65,13 50 55 27 97 38 49 65,13 50 55 27 38 97 49 65,13 50 55 27 38 49 97 65,13 50 55 27 38 49 6597,第二趟,13 50 27 55 38 49 6597,13 50 27 38 55 49 6597,13 50 27 38 49 55 65 97,pos=n,3. 起泡排序（改进）,2022/12/25,数据结构与STL,36,第三趟,13 27 50 38 49 55 65 97,13 27 38 50 49 55 65 97,13 27 38 49 50 55 65 97,第四趟,13 27 38 49 50 55 65 97,3. 起泡排序（改进）,具体过程1）初始状态无序区为r1.n2）对无序区从前向后，依次比较相邻记录，若反序则交换，并记录交换的位置pos。最后一次交换的位置pos，就是下一趟无序区r1.pos3）反复执行2），直到无序区中没有反序的记录,2022/12/25,37,数据结构与STL,3. 起泡排序（改进）,已知无序区r1.pos，则如何进行反序交换?int bound = pos; /带排序记录右边界pos=0; /标记，记录交换的位置 for (int i=1; iri+1) r0 = ri; ri=ri+1; ri+1=r0; pos =i; /记录最后交换的位置 ,2022/12/25,38,数据结构与STL,3. 起泡排序（改进）,void BubbleSort ( int r, int n) int pos = n; while (pos!=0)int bound = pos; /本次无序记录的范围pos = 0;for(int i=1;i ri+1)/ 相邻记录比较 r0 = ri;ri = ri+1; ri+1=r0; /交换pos = i; ,2022/12/25,39,数据结构与STL,3.起泡排序的性能分析,2022/12/25,40,数据结构与STL,最好情况正序序列：比较 移动最坏情况逆序序列：比较 移动平均情况时间复杂度 O(n2) 空间复杂度 O(1),n-1,0,4.快速排序,快速排序是起泡排序的改进改进着眼点 起泡排序：记录的比较和移动是在相邻位置进行，需要比较移动多次才能到最终的位置。 快速排序：记录的比较和移动从两端向中间进行的，记录移动的距离较远。,2022/12/25,41,数据结构与STL,4.快速排序,快速排序又叫分区交换排序，其基本思想：1. 选择一个记录作为轴值，将记录分成2部分。2. 分别对这两部分重复上述过程。,2022/12/25,42,数据结构与STL,递归,4.快速排序,需要解决的问题1. 如何选择基准记录？ 记录集中的第一个记录。2. 如何分区，使大于基准的记录后移，小于基准的记录前移？3. 如何判决快速排序结束？递归缩小分区，直到分区只有一个记录。,2022/12/25,43,数据结构与STL,2. 如何分区？,分区算法 初始化 取第一个记录R1作为基准 i 基准左侧待比较的记录， 初始i=1 j 基准右侧待比较的记录, 初始j=n 右侧扫描 从后向前找到第一个比基准小的记录，和基准交换 左侧扫描 从前到后找到第一个比基准大的记录，和基准交换 反复执行，直到i=j结束,2022/12/25,44,数据结构与STL,2. 如何分区？,2022/12/25,45,21,25,49,25*,16,08,0 1 2 3 4 5,pivot,j,i,数据结构与STL,2. 如何分区？,2022/12/25,46,一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。,数据结构与STL,一趟快速排序,int Partion(int r, int i, int j)int pivot=ri;while (i=pivot) j-;rj ri;while(ij) ,2022/12/25,47,数据结构与STL,5快速排序（改进）,改进出发点 一趟快速排序： 每交换一对记录需要进行三次移动，而实际上排序过程中对pivot的位置交换是多余的，只有i=j的位置才是pivot的位置。 所以，可以将pivot保存在r0中，排序过程中只有ri和rj移动。,2022/12/25,48,数据结构与STL,2）分区改进,分区算法 初始化 取第一个记录作为基准，保存在任意位置 i 基准左侧待比较的记录， 初始i=1 j 基准右侧待比较的记录, 初始j=n 右侧扫描 从后向前找到第一个比基准小的记录，移至位置i 左侧扫描 从前到后找到第一个比基准大的记录，移至位置j 反复执行，直到i=j结束，将r0移至ri。,2022/12/25,49,数据结构与STL,21,25,49,25*,16,08,0 1 2 3 4 5 6,pivot,j,i,21,2022/12/25,50,数据结构与STL,5快速排序（改进）,2022/12/25,51,一趟快速排序结束，待排序序列被分成两个子序列，再分别进行快速排序。,数据结构与STL,一趟快速排序（改进）,int Partion(int r , int first, int end)int i=first; int j=end; int pivot = ri; /选取基准记录while (i=pivot)/右侧扫描 j-;ri + = rj;while(ij) ,2022/12/25,52,数据结构与STL,5快速排序（改进）,2022/12/25,53,数据结构与STL,5.快速排序,void Qsort(int r, int i, int j)if ( ij )int pivotloc = Partion(r, i, j); Qsort( r, i, pivotloc-1); Qsort( r, pivotloc+1, j);,2022/12/25,54,数据结构与STL,5.快速排序的性能分析,最好情况每次划分的左侧序列和右侧序列的长度相同。表长为n的序列可划分log2n层。定位一个记录要对整个待划分序列扫描一遍，所需时间O(n)。 总的时间复杂度O(nlog2n)。,2022/12/25,55,数据结构与STL,5.快速排序的性能分析,2022/12/25,56,数据结构与STL,最坏情况待排序记录为逆序或正序，每次划分只得到比上一次少一个的子序列，此时必须要n-1次递归，第i 次需要n-i次比较，所以，总的比较次数： 记录的移动次数=比较次数，所以总的时间复杂度O(n2),5.快速排序的性能分析,平均性能时间复杂度O(nlog2n)栈的深度O(log2n)特点快速排序是一种不稳定的排序方法,2022/12/25,57,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,58,4. 选择排序,数据结构与STL,选择排序,主要内容 1存储结构 2简单选择排序 3堆排序,2022/12/25,59,数据结构与STL,1存储结构,排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。 int rn+1; r1,r2,rn选择排序的特征每趟排序在待排序序列中选择关键码最小的记录，添加到有序序列中。,2022/12/25,60,数据结构与STL,2.简单选择排序,基本思想 第 i 趟排序在无序序列ri.n 中选择关键码最小的记录，与ri交换，使有序序列不断增长直到全部排序完毕。,2022/12/25,61,r1r2 ri-1 |ri ri+1 rmin rn,有序区,无序区,交换,数据结构与STL,2.简单选择排序,2022/12/25,62,如何在ri.n中选择最小的记录？,数据结构与STL,2.简单选择排序,1）如何在无序区ri.n选择最小的记录? 假设无序区的ri是最小记录，附设一个变量index=i,然后依次将后续的记录与rindex比较，如果比rindex小，则index记录该位置。int index = i;/假设index是最小的for(int j=i+1; j=n; j+) /选择最小记录的位置if (rj rindex) index = j 2) 比较完毕，交换rindex和ri的记录。,2022/12/25,63,index记录无序区最小记录的位置,数据结构与STL,2.简单选择排序,void SelectSort(int r, int n)for(int i=1; in; i+) /n-1趟排序int index = i;/假设index是最小的 for(int j=i+1; j=n; j+)/查找最小记录的位置 if (rj rindex)index = j ;if (index!=i)/若第一个就是最小元素，则不用交换 r0=ri; ri=rindex; rindex =r0;/利用r0作为临时空间交换记录,2022/12/25,64,数据结构与STL,2.简单选择排序性能分析,特点移动次数最少，稳定的排序算法最好情况正序序列：比较移动最坏情况 序列：比较移动逆序序列-不是最坏 移动 平均情况时间复杂度 O(n2) 空间复杂度O(1),2022/12/25,数据结构与STL,65,0,3*(n-1),3*(n-1)/2,3. 堆排序,什么是堆？堆是具有下列性质的完全二叉树：小根堆：每个结点的值左右孩子结点的值大根堆：每个结点的值左右孩子结点的值 ki k2i ki k2i ki k2i+1 或 ki k2i+1,2022/12/25,66,数据结构与STL,3. 堆排序,小根堆大根堆,2022/12/25,67,( 10, 15, 56, 25, 30, 70 ),( 70, 56, 30, 25, 15, 10 ),堆的特点：根结点一定是最大或最小者,数据结构与STL,思考？,12, 36, 27, 65, 40, 14, 98, 81这个序列是不是堆？,2022/12/25,68,数据结构与STL,3. 堆排序,堆调整问题 一棵完全二叉树中，根结点的左右子树都是堆，如何调整根结点，使整棵二叉树成为一个堆？,2022/12/25,69,40,24,45,32,76,65,49,97,数据结构与STL,堆调整过程筛选,小根堆筛选：总是将根结点与左右孩子进行比较，若不满足堆的条件，则将根结点与较小的结点交换，一直到叶子结点，或所有子树均为堆为止。,2022/12/25,70,40,24,32,40,数据结构与STL,筛选算法,堆的存储结构顺序存储结构，ri是r2i r2i+1的父结点前提 1）要筛选的结点编号是k 2）堆中最后一个结点的编号是m 3）结点k的左右子树均为堆（即rk+1rm满足堆的条件）,2022/12/25,71,数据结构与STL,筛选算法(小根堆),void Sift (int r, int k, int m) int i=k， j=2*i; /i是要筛选的结点，j是i的左孩子 while (j rj+1) j+; /j 是左右孩子中较小者if (rirj) break; /符合小根堆的条件，结束else rirj ;/根结点与孩子结点交换 i = j; j= 2*i;,2022/12/25,72,数据结构与STL,4. 堆排序,什么是堆排序？1）将待排序的记录构造成一个堆2）输出堆顶元素3）将堆中最后一个元素移至堆顶，并将剩余元素调整成堆。反复执行2) 3)，直到堆中只有一个记录。,2022/12/25,73,数据结构与STL,4. 堆排序,将待排序的记录构造成一个堆？前提完全二叉树使用顺序序列存储步骤1）所有叶子结点都是堆2）从n/2个记录(最后一个分支结点)开始筛选3）直到根结点，结束,2022/12/25,74,数据结构与STL,4. 堆排序建堆（小根堆）,for (int i = n/2; i=1; i- )Sift ( r, i, n );,2022/12/25,75,49,97,65,13,13,49,49,27,数据结构与STL,4. 堆排序,如何输出堆顶元素？将堆顶元素和最后一个元素交换如何将剩余元素调整成堆？ 1)需要输出堆顶元素n-1次 2)则第i次，需要调整的元素范围r1.n-i,2022/12/25,76,数据结构与STL,4. 堆排序筛选（小根堆）,r1 rn;Sift ( r, 1, n-1 );,2022/12/25,77,13,97,27,97,49,97,输出堆顶元素,数据结构与STL,4. 堆排序筛选（小根堆）,r1 rn-1;Sift ( r, 1, n-2);,2022/12/25,78,97,27,97,49,38,输出堆顶元素,97,数据结构与STL,4. 堆排序筛选（小根堆）,r1 rn-2;Sift ( r, 1, n-3);,2022/12/25,79,输出堆顶元素,65,38,49,65,数据结构与STL,4. 堆排序筛选（小根堆）,r1 rn-i+1;Sift ( r, 1, n-i);,2022/12/25,80,输出堆顶元素,数据结构与STL,4. 堆排序算法,void Sift (int r, int k, int m) int i=k， j=2*i; /i是要筛选的结点，j是i的左孩子 while (j rj+1) j+; /j 是左右孩子中较小者 if (rirj ; /根结点与孩子结点交换 i = j; j= 2*i; ,2022/12/25,81,数据结构与STL,4. 堆排序性能分析,堆排序的时间消耗1. 建堆时间复杂度O(nlog2n)2. 重建堆时的筛选第i次输出堆顶记录重建堆的时间为O(log2(n-i)，需要n-1次输出堆顶元素。总的是间复杂度O(nlog2n)堆排序是一种不稳定的排序方法。,2022/12/25,82,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,83,5. 归并排序,数据结构与STL,归并排序,主要内容 1存储结构 2二路归并排序（非递归） 3二路归并排序（递归）,2022/12/25,84,数据结构与STL,1存储结构,排序使用顺序结构为了关注排序算法本身，所以本章所有排序的存储结构是0号位置留空的整型一维数组。 int rn;归并排序的特征将两个或两个以上的有序序列归并成一个有序序列的过程。,2022/12/25,85,数据结构与STL,归并排序,最简单的归并排序两路归并排序1）将n个记录的序列分成n个子集 2）将相邻的两个子合并成n/2个子集3）将相邻的两个子合并成n/4个子集合并成一个子集。,2022/12/25,86,数据结构与STL,2.二路归并排序,初始序列 (49) (38) (65) (97) (76) (13) (27),2022/12/25,87,一趟,二趟,三趟,数据结构与STL,2.二路归并排序,1.如何构造初始序列？将整个序列看成是长度为1的n个有序序列2.如何将相邻序列归并在一起？相邻序列rsrm和rm+1rt，归并成一个新序列r1sr1t。,2022/12/25,88,数据结构与STL,归并一次,void Merge (int r, int r1, int s, int m, int t) int i=s; /i指向rsm int j=m+1; /j指向rm+1t, int k=s; /k指向r1; while (i=m ,2022/12/25,89,数据结构与STL,归并一次,if (i=m) /若rsm没处理完 while (i=m) r1k+= ri+; if (j=t) /若rm+1t没处理完 while (j=t) r1k+= rj+;,2022/12/25,90,数据结构与STL,2.一趟归并（非递归）,1.分析 除最后一个序列外，其他序列的长度相同，用h表示把若干个长度为h的序列和最后一个=h的序列两两归并，把结果保存在r11.n中,2022/12/25,91,h,h,h,h,1,n,i,i,数据结构与STL,2.一趟归并（非递归）,三种情况,2022/12/25,92,数据结构与STL,2.一趟归并的算法（非递归）,void MergePass(int r,int r1, int n, int h) int i=1; while (i=n-2*h+1) /长度为h的序列两两归并 Merge( r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h+1) Merge( r, r1, i, i+h-1, n);/两个序列，其中一个h else for ( ; i= n;i+) /只有一个=h的序列 r1i =ri;,2022/12/25,93,数据结构与STL,2.归并排序的算法（非递归）,void MergeSort(int r, int r1, int n) int h = 1; while (hn) MergePass(r, r1 ,n, h); h=2*h; for (int i=1; i=n; i+) ri = r1i; ,2022/12/25,94,数据结构与STL,3.归并算法递归,2022/12/25,95,49 38 65 97 76 13 27,数据结构与STL,1.归并,void MergeSort (int r, int r1, int s, int t) int r2MAXSIZE; if (s=t) r1s = rs; else int m=(s+t)/2; /将r平分成rs.m 和rm+1.t MergeSort (r, r1, s, m); /递归的将rs.m 归并为r1s.m MergeSort ( r, r1, m+1, t); /递归的将rm+1.t 归并为r1m+1.t Merge( r1, r, s, m, t); / 将r1s.m 和r1m+1.t归并rs.t void main() /主函数中调用如下：int r12=5,3,7,2,9,10,12,4,30,8,1,6, int r112; MergeSort(r, r1, 0, 11);,2022/12/25,96,数据结构与STL,3归并排序的性能分析,时间性能 归并排序需要log2n趟，每趟需要把结果存在r1n中，需要O(n) 时间复杂度O(nlog2n)空间性能 空间复杂度 O(n)归并排序是稳定的排序方法,2022/12/25,97,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,98,6. 排序比较,数据结构与STL,各种排序的比较,2022/12/25,99,数据结构与STL,比较,时间性能1.快速排序：平均性能最好2.待排序序列较多： 归并排序 快于 堆排序 时间性能,2022/12/25,100,数据结构与STL,比较,稳定的排序：直接插入排序. 起泡排序. 简单选择排序. 归并排序不稳定的排序希尔排序. 快速排序. 堆排序,2022/12/25,101,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL中相关排序算法,2022/12/25,102,7. 外部排序,数据结构与STL,7. 外部排序,定义内部排序若整个排序过程中不涉及数据的内、外存交换，待排序的记录全部存放在内存中排序，称为内部排序。外部排序若待排序的的文件很大，就无法将整个文件的所有记录同时调入内存进行排序，只能将文件放在外存上，我们称这种排序为外部排序。,2022/12/25,103,数据结构与STL,7. 外部排序,基本思想内外存交换和“内部归并”主要步骤：1 将待排序记录分成若干长度为t的段R1、R2、Rn，t的长度应该足够长但不能超过可用来排序的内存空间；2 利用上述内部排序方法，对每一段进行内部排序，这些经过排序的段通常称为“顺串”，“顺串”生成后即写入外存；3 对这些“顺串”进行归并，使“顺串”的长度逐渐增大，直至待排序的记录成为一个顺串。,2022/12/25,104,数据结构与STL,第八章 排序,学习内容： 1. 概述 2. 插入排序 3. 交换排序 4. 选择排序 5. 归并排序6. 排序比较7. 外部排序8. STL 中相关排序算法,2022/12/25,105,8. STL 中相关排序算法,数据结构与STL,8. STL 中相关排序算法,STL sort算法函数包括：,2022/12/25,106,数据结构与STL,8. STL 中相关排序算法,STL排序算法的使用：排序算法的参数都需要输入范围，begin, end)。迭代器(iterator)必须是可以随机访问的迭代器RandomAccessIterator。如果需要自己定义比较函数，可以把事先定义好的仿函数(functor)作为参数传入。,2022/12/25,107,数据结构与STL,排序中的比较函数,当你需要按照某种特定方式进行排序时，你需要给sort指定比较函数，否则程序会自动提供给你一个比较函数，例如：vector vect; /. 插入元素sort(vect.begin(), vect.end(); 相当于调用sort(vect.begin(), vect.end(), less() );,2022/12/25,108,数据结构与STL,排序中的比较函数,STL中提供的仿函数包括：,2022/12/25,109,数据结构与STL,定义比较函数：class myclass public: myclass(int a, int b):first(a), second(b) int first; int second; bool operator (const myclass ,2022/12/25,110,数据结构与STL,全排序,Sort采用的是成熟的快速排序算法复杂度为n*log(n)stable_sort是稳定排序，采用的是归并排序算法复杂为n*log(n),2022/12/25,111,数据结构与STL,例如：定义比较函数：class studentpublic: student(const string ,2022/12/25,112,数据结构与STL,局部排序,局部排序其实是为了减少不必要的操作而提供的排序方式， STL中提供了partial_sort和partial_sort两种局部排序。partial_sort(vect.begin(), vect.begin()+5, vect.end(), less() ); partial_sort采用的堆排序（heapsort）复杂度是n*log(n),2022/12/25,113,数据结构与STL,指定元素排序,例如：班上有10个学生，我想知道分数排在倒数第4名的学生。 nth_element(vect.begin(), vect.begin()+3, vect.end(), less();,2022/12/25,114,数据结构与STL,Sort 和容器,sort函数对于下面三个容器是可用的：1）vector2）string3）deque 对于list容器list自带一个sort成员函数list:sort(). 它和算法函数中的sort差不多，但是list:sort是基于指针的方式排序。,2022/12/25,115,数据结构与STL,Sort 和容器,排序算法的效率（效率由高到低）1）partion 2）stable_partition 3）nth_element 4）partial_sort 5）sort 6）stable_sort,2022/12/25,116,数据结构与STL,