数据结构第7章.pptx

17.1 排序术语及记号术语术语 记录记录记录记录结点结点结点结点 文件文件文件文件线性表线性表线性表线性表 关键码：关键码：关键码：关键码：能够唯一确定结点的一个或若干域。能够唯一确定结点的一个或若干域。能够唯一确定结点的一个或若干域。能够唯一确定结点的一个或若干域。排序码：排序码：排序码：排序码：作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。组合排序码，组合排序码，组合排序码，组合排序码，(主关键码，次关键码主关键码，次关键码主关键码，次关键码主关键码，次关键码)例，例，例，例，(总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数)排序：排序：排序：排序：将一组杂乱无章的数据按一定的规律排列起来将序列中的记录。将一组杂乱无章的数据按一定的规律排列起来将序列中的记录。将一组杂乱无章的数据按一定的规律排列起来将序列中的记录。将一组杂乱无章的数据按一定的规律排列起来将序列中的记录。第1页/共80页2术语排序问题排序问题排序问题排序问题 给定一组记录序列给定一组记录序列给定一组记录序列给定一组记录序列R=rR=rR=rR=r1 1 1 1,r,r,r,r2 2 2 2,.r.r.r.rn n n n,其排序码分别为其排序码分别为其排序码分别为其排序码分别为K=K=K=K=k k k k1 1 1 1,k,k,k,k2 2 2 2,，k k k kn n n n 将这些记录排成顺序为将这些记录排成顺序为将这些记录排成顺序为将这些记录排成顺序为R R R R=r r r rs1s1s1s1,r,r,r,rs2s2s2s2,，r r r rsn sn sn sn 的一个序列的一个序列的一个序列的一个序列S S S S，其排序码序列其排序码序列其排序码序列其排序码序列K K K K=k k k ks1s1s1s1，k k k ks2s2s2s2，k k k ksn sn sn sn 是一个满足某种关系的有序序列是一个满足某种关系的有序序列是一个满足某种关系的有序序列是一个满足某种关系的有序序列。关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。第2页/共80页3术语 内排序内排序内排序内排序全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。外排序外排序外排序外排序排序过程还要访问外存排序过程还要访问外存排序过程还要访问外存排序过程还要访问外存(因为待排记录的因为待排记录的因为待排记录的因为待排记录的数量太大，内存容纳不下数量太大，内存容纳不下数量太大，内存容纳不下数量太大，内存容纳不下)排序算法的稳定排序算法的稳定排序算法的稳定排序算法的稳定&不稳定不稳定不稳定不稳定 如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象riririri和和和和rjrjrjrj，它们的关键码它们的关键码它们的关键码它们的关键码 ki=kjki=kjki=kjki=kj，且在排序之前，对象且在排序之前，对象且在排序之前，对象且在排序之前，对象riririri排在排在排在排在rjrjrjrj前面。前面。前面。前面。如果在排序之后，对象如果在排序之后，对象如果在排序之后，对象如果在排序之后，对象riririri仍在对象仍在对象仍在对象仍在对象rjrjrjrj的前面，则称这的前面，则称这的前面，则称这的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。个排序方法是稳定的，否则称这个排序方法是不稳定的。个排序方法是稳定的，否则称这个排序方法是不稳定的。个排序方法是稳定的，否则称这个排序方法是不稳定的。第3页/共80页4基本操作按排序依据原则按排序依据原则按排序依据原则按排序依据原则插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、希尔（希尔（希尔（希尔（shellshellshellshell）排序）排序）排序）排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序归并排序：归并排序：归并排序：归并排序：2-2-2-2-路归并排序路归并排序路归并排序路归并排序基数排序基数排序基数排序基数排序第4页/共80页57.2 三种代价为O(n2)的排序方法 7.2.1 7.2.1 7.2.1 7.2.1 插入排序插入排序插入排序插入排序 7.2.7.2.7.2.7.2.2 2 2 2 冒泡冒泡冒泡冒泡排序排序排序排序 7.2.7.2.7.2.7.2.3 3 3 3 选择选择选择选择排序排序排序排序第5页/共80页67.2.1 7.2.1 插入排序插入排序算法思想：逐个处理待排序的记录，每个记录都要与前面那些已排好序的记录进行比较，然后插入到适当的位置。第6页/共80页77.2.1 教材上插入排序算法template template template template void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)for(int i=1;in;i+)for(int i=1;in;i+)for(int i=1;in;i+)for(int i=1;i0)&for(int j=i;(j0)&for(int j=i;(j0)&for(int j=i;(j0)&(Comp:lt(Aj,Aj-1);j-)(Comp:lt(Aj,Aj-1);j-)(Comp:lt(Aj,Aj-1);j-)(Comp:lt(Aj,Aj-1);j-)swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定 空间代价：空间代价：空间代价：空间代价：(1)(1)(1)(1)时间代价：时间代价：时间代价：时间代价：最佳情况：最佳情况：最佳情况：最佳情况：n-1n-1n-1n-1次次次次比较比较比较比较，0 0 0 0次次次次交换交换交换交换，(n)(n)(n)(n)最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为i=n(n-1)/2=i=n(n-1)/2=i=n(n-1)/2=i=n(n-1)/2=(n(n(n(n2 2 2 2)交换次数为交换次数为交换次数为交换次数为 3i=3n(n-1)/2=3i=3n(n-1)/2=3i=3n(n-1)/2=3i=3n(n-1)/2=(n(n(n(n2 2 2 2)（一次（一次（一次（一次swapswapswapswap需需需需要交换要交换要交换要交换3 3 3 3次）次）次）次）平均情况：平均情况：平均情况：平均情况：(n(n(n(n2 2 2 2)i=1n-1i=1n-1第7页/共80页8改进的插入排序算法template template template template void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)for(int i=1;in;i+)for(int i=1;in;i+)for(int i=1;in;i+)for(int i=1;i=0&(Comp:lt(while(j=0&(Comp:lt(while(j=0&(Comp:lt(while(j=0&(Comp:lt(temptemptemptemp,Aj),Aj),Aj),Aj)Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=Aj;j-;/将将将将=Ai=Ai=Ai=Ai的记录后移的记录后移的记录后移的记录后移 Aj+1=temp;Aj+1=temp;Aj+1=temp;Aj+1=temp;/Aj+1/Aj+1/Aj+1/Aj+1是记录是记录是记录是记录AiAiAiAi的正确位置的正确位置的正确位置的正确位置 第8页/共80页9改进插入排序算法分析 算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定 空间代价：空间代价：空间代价：空间代价：(1)(1)(1)(1)时间代价：时间代价：时间代价：时间代价：最佳情况：最佳情况：最佳情况：最佳情况：n-1n-1n-1n-1次比较，次比较，次比较，次比较，n n n n次交换，次交换，次交换，次交换，(n)(n)(n)(n)最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为(n(n(n(n2 2 2 2)（同前）（同前）（同前）（同前）交换次数为交换次数为交换次数为交换次数为 i=n(n-1)/2=i=n(n-1)/2=i=n(n-1)/2=i=n(n-1)/2=(n(n(n(n2 2 2 2)平均情况：平均情况：平均情况：平均情况：(n(n(n(n2 2 2 2)i=1n-1第9页/共80页10加入监视哨的插入排序算法template template template template void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)void inssort(Elem A,int n)for(int i=2;i=n;i+)for(int i=2;i=n;i+)for(int i=2;i=n;i+)for(int i=2;i=n;i+)A0=Ai;A0=Ai;A0=Ai;A0=Ai;/数组有效存储从数组有效存储从数组有效存储从数组有效存储从A1A1A1A1开始开始开始开始 j=i-1;j=i-1;j=i-1;j=i-1;while(Comp:lt(A0,Aj)while(Comp:lt(A0,Aj)while(Comp:lt(A0,Aj)while(Comp:lt(A0,Aj)Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=A0;Aj+1=A0;Aj+1=A0;Aj+1=A0;第10页/共80页11利用二分法的插入排序思想：在插入第i个记录时，前面的记录已经有序。故可以用二分法查找第i个记录的正确位置。第11页/共80页127.2.2 起泡排序算法思想：若序列中有n 个元素，通常进行n-1 趟。第1 趟，针对第Vector0 至Vectorn-1个元素进行。第2 趟，针对第Vector1至Vectorn-1 个元素进行第n-1 趟，针对第Vectorn-2至Vectorn-1 个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确，则进行交换；否则继续比较下面两个相邻的元素。第12页/共80页137.2.2 起泡排序不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。第13页/共80页14教材上起泡排序算法template template template template void bubsort(Elem A,int n)void bubsort(Elem A,int n)void bubsort(Elem A,int n)void bubsort(Elem A,int n)for(int i=0;for(int i=0;for(int i=0;for(int i=0;in-1in-1in-1ii;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);第14页/共80页15起泡排序算法分析 稳定 空间代价：(1)（此章我们仅分析排序所需额外空间开销）时间代价：比较次数：最佳、最差i=n(n-1)/2=(n2)交换次数最多为(n2)，最少为0，平均为(n2)。最大，最小，平均时间代价均为(n2)。1i=n-1第15页/共80页16优化的起泡算法改进：检查每次起泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序，排序结束。避免不必要的比较。第16页/共80页17改进的起泡排序算法template template template template void bubsort(Elem A,int n)void bubsort(Elem A,int n)void bubsort(Elem A,int n)void bubsort(Elem A,int n)int int int int flagflagflagflag;for(int i=0;in-1;i+)for(int i=0;in-1;i+)for(int i=0;in-1;i+)for(int i=0;ii;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)if(Comp:lt(Aj,Aj-1)swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);flag=TRUEflag=TRUEflag=TRUEflag=TRUE;if(if(if(if(flag=FALSEflag=FALSEflag=FALSEflag=FALSE)return;)return;)return;)return;第17页/共80页18优化起泡排序算法分析 算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定 时间代价：时间代价：时间代价：时间代价：最佳情况：最佳情况：最佳情况：最佳情况：n-1n-1n-1n-1次比较，次比较，次比较，次比较，0 0 0 0次交换，次交换，次交换，次交换，(n)(n)(n)(n)最差情况：比较和交换次数均为最差情况：比较和交换次数均为最差情况：比较和交换次数均为最差情况：比较和交换次数均为(n(n(n(n2 2 2 2)平均情况：平均情况：平均情况：平均情况：(n(n(n(n2 2 2 2)第18页/共80页197.2.3 直接选择排序算法思想：找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，比起泡排序减少了移动次数。第19页/共80页20直接选择排序算法template template template template void selsort(Elem A,int n)void selsort(Elem A,int n)void selsort(Elem A,int n)void selsort(Elem A,int n)for(int i=0;in-1;i+)for(int i=0;in-1;i+)for(int i=0;in-1;i+)for(int i=0;ii;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)for(int j=n-1;ji;j-)/Find least/Find least/Find least/Find least if(Comp:lt(Aj,Alowindex)if(Comp:lt(Aj,Alowindex)if(Comp:lt(Aj,Alowindex)if(Comp:lt(Aj,Alowindex)lowindex=jlowindex=jlowindex=jlowindex=j;/Put it in place/Put it in place/Put it in place/Put it in place swap(A,i,swap(A,i,swap(A,i,swap(A,i,lowindexlowindexlowindexlowindex););););第20页/共80页21算法分析 不 稳定 空间代价：(1)时间代价：比较次数：最好、最坏情况均为(n-i-1)=n*(n-1)/2，即(n2)交换次数：最好（自身交换）、最坏3(n-1)（一次swap需要交换3次），故(n)总时间代价：(n2)。i=0n-2第21页/共80页22交换指针，减少交换记录的次数第22页/共80页23小结：时间代价第23页/共80页24小结：时间代价（2）时间复杂度为(n2)的原因：一个长度为n序列平均有n(n-1)/4对逆置任何一种只对相邻记录进行比较的排序算法的平均时间代价都是(n2)第24页/共80页257.3 Shell 排序（希尔排序）直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价为(n)对于短序列，直接插入排序比较有效 Shell排序有效地利用了直接插入排序的这两个性质第25页/共80页26Shell 排序算法思想：先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序，从而完成排序第26页/共80页27Shell 排序 又名：缩小增量排序法又名：缩小增量排序法又名：缩小增量排序法又名：缩小增量排序法(不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价(n n n n1.51.51.51.5)）n n n n很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快第27页/共80页28shell排序算法（增量除以2递减）/Modified version of Insertion SortModified version of Insertion Sorttemplate template void void inssort2inssort2(Elem A,int n,int incr)(Elem A,int n,int incr)for(int i=incr;in;i+=incr)for(int i=incr;i=incr)&(Comp:lt(Aj,Aj-incr);(j=incr)&(Comp:lt(Aj,Aj-incr);j-=incr)j-=incr)swap(A,j,j-incr);swap(A,j,j-incr);template template void void shellsortshellsort(Elem A,int n)(Elem A,int n)/Shellsort/Shellsort for(int i=n/2;i2;i/=2)for(int i=n/2;i2;i/=2)/For each incr/For each incr for(int j=0;ji;j+)for(int j=0;ji;j+)/Sort sublists/Sort sublists inssort2(inssort2(&Aj,n-j,i&Aj,n-j,i););inssort2(A,n,1);inssort2(A,n,1);第28页/共80页29算法分析 不 稳定 空间代价：(1)时间代价：增量每次除以2递减，则为(n2)选择合适的增量序列，可以使时间代价接近：(n)。第29页/共80页30Shell排序增量选择问题增量每次除以2递减时，效率仍然为(n2)问题：选取的增量之间并不互质 间距为2k-1的子序列都是由那些间距为2k的子序列组成的 上一轮循环中这些子序列都已经排过序了，导致处理效率不高第30页/共80页31 Hibbard增量序列 2k-1，2k-1-1，7，3，1，Shell(3)和Hibbard增量序列的Shell排序的效率可以达到(n3/2)选取其他增量序列还可以更进一步减少时间代价第31页/共80页327.4 快速排序分治法排序：将原始数组分为若干个子部分，然后分别进行排序。分治策略的实例BST查找、插入、删除算法快速排序、归并排序二分检索主要思想划分求解子问题(子问题不重叠)综合子问题解，成为问题的解第32页/共80页33快速排序算法思想算法思想：若序列中有n 个元素，任选一个关键字作为轴值，将序列分成两部分。其中左半部分的结点的关键字小于等于轴值，右半部分的结点的关键字大于轴值，然后对左右两部分分别进行类似的处理，直至排好序为止。关键问题：选择轴值（pivot）将序列划分为两个子序列L和R，使得L中所有记录都小于或等于轴值，R中记录都大于轴值对子序列L和R递归进行快速排序第33页/共80页34快速排序示例第34页/共80页35轴值选择分割过程整个快速排序的关键，轴值位于正确位置，分割后使得：L中所有记录位于轴值左边 R中记录位于轴值右边轴值选择尽可能使L，R长度相等选择策略：选择最左边记录随机选择选择平均值第35页/共80页36一次分割过程选择轴值并存储轴值最后一个元素放到轴值位置初始化下标i,j，分别指向头尾i递增直到遇到比轴值大的元素，将此元素覆盖到j的位置；j递减直到遇到比轴值小的元素，将此元素覆盖到i的位置重复上一步直到i=j，将轴值放到i的位置，完毕第36页/共80页37快速排序实例 初始序列：初始序列：72 6 57 88 60 42 83 73 48 8572 6 57 88 60 42 83 73 48 85轴值60606060606060第37页/共80页38快速排序算法（教材 p149-150)template template template template void void void void qsortqsortqsortqsort(Elem A,int i,int j)(Elem A,int i,int j)(Elem A,int i,int j)(Elem A,int i,int j)if(j=i)return;if(j=i)return;if(j=i)return;if(j=i)return;/List too smallList too smallList too smallList too small，序列元，序列元，序列元，序列元素小于等于素小于等于素小于等于素小于等于1 1 1 1时时时时 int pivotindex=findpivot(A,i,j);int pivotindex=findpivot(A,i,j);int pivotindex=findpivot(A,i,j);int pivotindex=findpivot(A,i,j);swap(A,pivotindex,j);swap(A,pivotindex,j);swap(A,pivotindex,j);swap(A,pivotindex,j);/Put pivot at end/Put pivot at end/Put pivot at end/Put pivot at end /k will be first position on right side/k will be first position on right side/k will be first position on right side/k will be first position on right side int k=partition(A,i-1,j,Aj);int k=partition(A,i-1,j,Aj);int k=partition(A,i-1,j,Aj);int k=partition(A,i-1,j,Aj);swap(A,k,j);swap(A,k,j);swap(A,k,j);swap(A,k,j);/Put pivot in place/Put pivot in place/Put pivot in place/Put pivot in place qsort(A,i,qsort(A,i,qsort(A,i,qsort(A,i,k-1k-1k-1k-1););););qsort(A,qsort(A,qsort(A,qsort(A,k+1k+1k+1k+1,j);,j);,j);,j);template template template template int int int int findpivotfindpivotfindpivotfindpivot(Elem A,int i,int j)(Elem A,int i,int j)(Elem A,int i,int j)(Elem A,int i,int j)/寻找轴值寻找轴值寻找轴值寻找轴值 return(i+j)/2;return(i+j)/2;return(i+j)/2;return(i+j)/2;第38页/共80页39快速排序算法（教材 p150)template template template template int int int int partitionpartitionpartitionpartition(Elem A,int l,int r,Elem&(Elem A,int l,int r,Elem&(Elem A,int l,int r,Elem&(Elem A,int l,int r,Elem&pivot)pivot)pivot)pivot)do do do do /Move the bounds in until they meet/Move the bounds in until they meet/Move the bounds in until they meet/Move the bounds in until they meet while(Comp:lt(A+l,pivot);while(Comp:lt(A+l,pivot);while(Comp:lt(A+l,pivot);while(Comp:lt(A+l,pivot);/l/l/l/l右移右移右移右移1 1 1 1位位位位 while(r!=0)&Comp:gt(A-r,pivot);while(r!=0)&Comp:gt(A-r,pivot);while(r!=0)&Comp:gt(A-r,pivot);while(r!=0)&Comp:gt(A-r,pivot);swap(A,l,r);swap(A,l,r);swap(A,l,r);swap(A,l,r);/Swap out-of-place values/Swap out-of-place values/Swap out-of-place values/Swap out-of-place values while(l r);while(l r);while(l r);while(l r);/Stop when they cross/Stop when they cross/Stop when they cross/Stop when they cross swap(A,l,r);swap(A,l,r);swap(A,l,r);swap(A,l,r);/Reverse last swap/Reverse last swap/Reverse last swap/Reverse last swap return l;return l;return l;return l;/Return first pos on right/Return first pos on right/Return first pos on right/Return first pos on right 第39页/共80页40轴 值 选 在 最 左第40页/共80页41快速排序算法分析（1）n-1k=1不稳定算法时间复杂度（交换次数远小于比较次数，主要考虑比较次数）最差情况：轴值总是为当前序列的最小值或者最大值。k=(n2).轴值10，共比较7次轴值20，共比较6次 轴值60，共比较2次轴值70，共比较1次原因：轴值选择不当。改进：随机选取轴值或最左、最右、中间三个元素中的值处于中间的作为轴值，通常可以避免最坏情况。第41页/共80页42快速排序算法分析（2）最佳情况：轴值总是将当前序列均分为2个子序列。共经过logn次分割，故(nlog n)第42页/共80页43快速排序算法分析（3）假设在每次分割时，轴值处于最终排序好的数组中位置的概率是一样的。也就是说，轴值将数组分成长度为0和n-1，1和n-2，的子序列的概率是相等的，都为1/n长度为n的序列，时间为T(n)，T(0)=T(1)=1，设选择轴值时间为常数分割时间为cn分割后长度分别为k 和n-1-k对子序列进行快速排序所需时间分别为T(k)和T(n-1-k)求解递推方程T(n)=cn+1/n*(T(k)+T(n1k)=cn+2/n*T(k)n-1k=0n-1k=0第43页/共80页44快速排序算法分析（4）最差情况：时间代价：(n2)空间代价（系统占用堆栈空间代价）：(n)最佳情况：时间代价：(nlog n)空间代价：(log n)平均情况：时间代价：(nlog n)空间代价：(log n)第44页/共80页45优化的快速排序可能优化：轴值选择小子串不递归子数组小于某个长度（阈值n=9）时，不递归块与块之间有序最后对整个数组进行一次插入排序消除递归避免进出栈、恢复断点等工作。速度加快。第45页/共80页467.5 归并排序算法思想简单地将原始序列划分为两个子序列分别对每个子序列递归排序最后将排好序的子序列合并为一个有序序列，即归并过程第46页/共80页477.5 归并排序List mergesort(List inlist)List mergesort(List inlist)List mergesort(List inlist)List mergesort(List inlist)/伪码框架伪码框架伪码框架伪码框架 if(inlist.length()=1)return inlist;if(inlist.length()=1)return inlist;if(inlist.length()=1)return inlist;if(inlist.length()=1)return inlist;List l1=half of the items from inlist;List l1=half of the items from inlist;List l1=half of the items from inlist;List l1=half of the items from inlist;List l2=other half of items from inlist;List l2=other half of items from inlist;List l2=other half of items from inlist;List l2=other half of items from inlist;return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);第47页/共80页48归并排序算法（教材p154）template template template template void void void void mergesortmergesortmergesortmergesort(Elem A,Elem temp,int left,int(Elem A,Elem temp,int left,int(Elem A,Elem temp,int left,int(Elem A,Elem temp,int left,int right)right)right)right)int mid=(left+right)/2;int mid=(left+right)/2;int mid=(left+right)/2;int mid=(left+right)/2;if(left=right)return;if(left=right)return;if(left=right)return;if(left=right)return;/1/1/1/1个元素则返回个元素则返回个元素则返回个元素则返回 mergesort(A,temp,left,mergesort(A,temp,left,mergesort(A,temp,left,mergesort(A,temp,left,midmidmidmid););););mergesort(A,temp,mergesort(A,temp,mergesort(A,temp,mergesort(A,temp,mid+1mid+1mid+1mid+1,right);,right);,right);,right);for(int i=left;i=right;i+)for(int i=left;i=right;i+)for(int i=left;i=right;i+)for(int i=left;i=right;i+)/Copy/Copy/Copy/Copy 子数组子数组子数组子数组 to to to to 临临临临时数组时数组时数组时数组temptemptemptemp tempi=Ai;tempi=Ai;tempi=Ai;tempi=Ai;int i1=left;int i2=mid+1;int i1=left;int i2=mid+1;int i1=left;int i2=mid+1;int i1=left;int i2=mid+1;for(int curr=left;curr=right;curr+)for(int curr=left;curr=right;curr+)for(int curr=left;curr=right;curr+)for(int curr=left;curr right)else if(i2 right)else if(i2 right)else if(i2 right)/Right exhausted/Right exhausted/Right exhausted/Right exhausted Acurr=tempi1+;Acurr=tempi1+;Acurr=tempi1+;Acurr=tempi1+;else if(Comp:lt(tempi1,tempi2)else if(Comp:lt(tempi1,tempi2)else if(Comp:lt(tempi1,tempi2)else if(Comp:lt(tempi1,tempi2)Acurr=tempi1+;Acurr=tempi1+;Acurr=tempi1+;Acurr=tempi1+;else Acurr=tempi2+;else Acurr=tempi2+;else Acurr=tempi2+;else Acurr=tempi2+;第48页/共80页49优化归并排序同优化的快速排序一样，对基本已排序序列直接插入排序归并时从两端开始处理，向中间推进第49页/共80页50优化归并