数据结构第7章..ppt

《数据结构第7章..ppt》由会员分享，可在线阅读，更多相关《数据结构第7章..ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 内排序 l7.1 排序术语及记号排序术语及记号l7.2 三种代价为三种代价为O(n2)的排序方法的排序方法l7.3 shell排序排序l7.4 快速排序快速排序l7.5 归并排序归并排序l7.6 堆排序堆排序l7.7 分配排序和基数排序分配排序和基数排序l7.8 对各种排序算法的实验比较对各种排序算法的实验比较l7.9 排序问题的下限排序问题的下限17.1 排序术语及记号排序术语及记号术语术语 l l记录记录记录记录结点结点结点结点 文件文件文件文件线性表线性表线性表线性表 l l关键码：关键码：关键码：关键码：能够唯一确定结点的一个或若干域。能够唯一确定结点的一个或若干域。能够唯一确

2、定结点的一个或若干域。能够唯一确定结点的一个或若干域。l l排序码：排序码：排序码：排序码：作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。作为排序运算依据的一个或若干域。l l组合排序码，组合排序码，组合排序码，组合排序码，(主关键码，次关键码主关键码，次关键码主关键码，次关键码主关键码，次关键码)例，例，例，例，(总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数)l l排序：排序：排序：排序：将一组杂乱无章的数据按一定的规律排列将一组杂乱无章的数据按一定的

3、规律排列将一组杂乱无章的数据按一定的规律排列将一组杂乱无章的数据按一定的规律排列起来将序列中的记录。起来将序列中的记录。起来将序列中的记录。起来将序列中的记录。2术语排序问题排序问题排序问题排序问题l l给定一组记录序列给定一组记录序列给定一组记录序列给定一组记录序列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 l l将这些记录排成顺序为将这些记录排成顺序为将这些记录排成顺序为

4、将这些记录排成顺序为R=R=R=R=r r r rs1s1s1s1,r,r,r,rs2s2s2s2,，r r r rsnsnsnsn 的一个的一个的一个的一个序列序列序列序列S S S S，其排序码序列其排序码序列其排序码序列其排序码序列K=K=K=K=k k k ks1s1s1s1，k k k ks2s2s2s2，k k k ksnsnsnsn 是一是一是一是一个满足某种关系的有序序列个满足某种关系的有序序列个满足某种关系的有序序列个满足某种关系的有序序列。关系是任意的，如通常经常使用的小于、大于等关系或任意的关系。3术语l l内排序内排序内排序内排序全部记录都可以同时调入内存进行的排序。全

5、部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。l l外排序外排序外排序外排序排序过程还要访问外存排序过程还要访问外存排序过程还要访问外存排序过程还要访问外存(因为待排记录的数因为待排记录的数因为待排记录的数因为待排记录的数量太大，内存容纳不下量太大，内存容纳不下量太大，内存容纳不下量太大，内存容纳不下)l l排序算法的稳定排序算法的稳定排序算法的稳定排序算法的稳定&不稳定不稳定不稳定不稳定如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象riririri 和和和和rjrjrj

6、rj ，它们的关键码它们的关键码它们的关键码它们的关键码 kikikiki=kjkjkjkj ，且在排序之前，对象且在排序之前，对象且在排序之前，对象且在排序之前，对象riririri 排在排在排在排在rjrjrjrj 前面。如果前面。如果前面。如果前面。如果在排序之后，对象在排序之后，对象在排序之后，对象在排序之后，对象riririri 仍在对象仍在对象仍在对象仍在对象rjrjrjrj 的前面，则称这个排序方的前面，则称这个排序方的前面，则称这个排序方的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。法是稳定的，否则称这个排序方法是不稳定的。法是稳定的，否则称这个排序方法是不稳

7、定的。法是稳定的，否则称这个排序方法是不稳定的。4基本操作按排序依据原则按排序依据原则按排序依据原则按排序依据原则插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、插入排序：直接插入排序、折半插入排序、希尔（希尔（希尔（希尔（shellshellshellshell）排序）排序）排序）排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序归并排序：归并

8、排序：归并排序：归并排序：2-2-2-2-路归并排序路归并排序路归并排序路归并排序基数排序基数排序基数排序基数排序57.2 三种代价为三种代价为O(n2)的排序方法的排序方法l l7.2.1 7.2.1 7.2.1 7.2.1 插入排序插入排序插入排序插入排序l l7.2.7.2.7.2.7.2.2 2 2 2 冒泡冒泡冒泡冒泡排序排序排序排序l l7.2.7.2.7.2.7.2.3 3 3 3 选择选择选择选择排序排序排序排序67.2.1 7.2.1 插入排序插入排序l算法思想：逐个处理待排序的记录，每个记录都要与前面那些已排好序的记录进行比较，然后插入到适当的位置。77.2.1 教材上插入

9、排序算法template template template template void void void void inssort(Eleminssort(Eleminssort(Eleminssort(Elem A,A,A,A,intintintint n)n)n)n)for(for(for(for(intintintint i=1;in;i+)i=1;in;i+)i=1;in;i+)i=1;i0)&j=i;(j0)&j=i;(j0)&j=i;(j0)&(Comp:lt(AjComp:lt(AjComp:lt(AjComp:lt(Aj,Aj-1);j-),Aj-1);j-),Aj-1);

10、j-),Aj-1);j-)swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);l l算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定空间代价：空间代价：空间代价：空间代价：(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)/

11、2=i=n(n-1)/2=(n(n(n(n2 2 2 2)交换次数为交换次数为交换次数为交换次数为 3 3 3 3i=3n(n-1)/2=i=3n(n-1)/2=i=3n(n-1)/2=i=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-18改进的插入排序算法template template template template void void void void inssor

12、t(Eleminssort(Eleminssort(Eleminssort(Elem A,A,A,A,intintintint n)n)n)n)for(for(for(for(intintintint i=1;in;i+)i=1;in;i+)i=1;in;i+)i=1;i=0&(while(j=0&(while(j=0&(while(j=0&(Comp:lt(Comp:lt(Comp:lt(Comp:lt(temptemptemptemp,Aj),Aj),Aj),Aj)Aj+1=Aj+1=Aj+1=Aj+1=Aj;jAj;jAj;jAj;j-;-;-;-;/将将将将=AiAiAiAi 的记录后

13、移的记录后移的记录后移的记录后移 Aj+1=temp;Aj+1=temp;Aj+1=temp;Aj+1=temp;/Aj+1/Aj+1/Aj+1/Aj+1是记录是记录是记录是记录AiAiAiAi 的正确位置的正确位置的正确位置的正确位置 9改进插入排序算法分析l l算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定空间代价：空间代价：空间代价：空间代价：(1)(1)(1)(1)时间代价：时间代价：时间代价：时间代价：最佳情况：最佳情况：最佳情况：最佳情况：n-1n-1n-1n-1次比较，次比较，次比较，次比较，n n n n次交换，次交换，次交换，次交换，(n)(n)(n)(n)最差情况

14、：比较次数为最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为(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-110加入监视哨的插入排序算法template template template template void void void void inssort(Eleminssort(Eleminssort(Elemins

15、sort(Elem A,A,A,A,intintintint n)n)n)n)for(for(for(for(intintintint i=2;i=n;i+)i=2;i=n;i+)i=2;i=n;i+)i=2;i=n;i+)A0=A0=A0=A0=AiAiAiAi;/数组有效存储从数组有效存储从数组有效存储从数组有效存储从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=A

16、j;j-;Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=A0;Aj+1=A0;Aj+1=A0;Aj+1=A0;11利用二分法的插入排序l思想：在插入第i个记录时，前面的记录已经有序。故可以用二分法查找第i个记录的正确位置。127.2.2 起泡排序算法思想：l若序列中有n 个元素，通常进行n-1 趟。l第1 趟，针对第Vector0 至Vectorn-1个元素进行。第2 趟，针对第Vector1至Vectorn-1 个元素进行第n-1 趟，针对第Vectorn-2至Vectorn-1 个元素进行。l每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确，则进

17、行交换；否则继续比较下面两个相邻的元素。137.2.2 起泡排序l不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。14教材上起泡排序算法template template template template void void void void bubsort(Elembubsort(Elembubsort(Elembubsort(Elem A,A,A,A,intintintint n)n)n)n)for(for(for(for(intintintint i=0;i=0;i=0;i=0;in-1in-1in-1ii;j-)j=n-1;ji;j-)j=n-

18、1;ji;j-)j=n-1;ji;j-)if(if(if(if(Comp:lt(AjComp:lt(AjComp:lt(AjComp:lt(Aj,Aj-1),Aj-1),Aj-1),Aj-1)swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);swap(A,j,j-1);15起泡排序算法分析l 稳定l 空间代价：(1)（此章我们仅分析排序所需额外空间开销此章我们仅分析排序所需额外空间开销）l 时间代价：比较次数：最佳、最差i=n(n-1)/2=(n2)交换次数最多为(n2)，最少为0，平均为(n2)。最大，最小，平均时间代价均为(n2)。1i=n-116优化的起

19、泡算法l改进：检查每次起泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序，排序结束。l避免不必要的比较。17改进的起泡排序算法template template template template void void void void bubsort(Elembubsort(Elembubsort(Elembubsort(Elem A,A,A,A,intintintint n)n)n)n)intintintint flagflagflagflag;for(for(for(for(intintintint i=0;in-1;i+)i=0;in-1;i+)i=0;in-1;i+)i=0

20、;ii;j-)j=n-1;ji;j-)j=n-1;ji;j-)j=n-1;ji;j-)if(if(if(if(Comp:lt(AjComp:lt(AjComp:lt(AjComp:lt(Aj,Aj-1),Aj-1),Aj-1),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;18优化

21、起泡排序算法分析l l算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定时间代价：时间代价：时间代价：时间代价：最佳情况：最佳情况：最佳情况：最佳情况：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)197.2.3 直接选择排序算法思想：找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交

22、换，比起泡排序减少了移动次数。20直接选择排序算法template template template template void void void void selsort(Elemselsort(Elemselsort(Elemselsort(Elem A,A,A,A,intintintint n)n)n)n)for(for(for(for(intintintint i=0;in-1;i+)i=0;in-1;i+)i=0;in-1;i+)i=0;ii;j-)j=n-1;ji;j-)j=n-1;ji;j-)j=n-1;ji;j-)/Find least/Find least/Find le

23、ast/Find least if(if(if(if(Comp:lt(AjComp:lt(AjComp:lt(AjComp:lt(Aj,AlowindexAlowindexAlowindexAlowindex)lowindexlowindexlowindexlowindex=j=j=j=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););););21算法分析l 不 稳定l

24、 空间代价：(1)l 时间代价：比较次数：最好、最坏情况均为(n-i-1)=n*(n-1)/2，即(n2)交换次数：最好（自身交换）、最坏3(n-1)（一次swap需要交换3次），故(n)总时间代价：(n2)。i=0n-222交换指针，减少交换记录的次数23小结：时间代价24小结：时间代价（2）l时间复杂度为(n2)的原因：的原因：一个长度为n序列平均有n(n-1)/4对逆置任何一种只对相邻记录进行比较的排序算法的平均时间代价都是(n2)257.3 Shell 排序（希尔排序）l 直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价为(n)对于短序列，直接插入排序比较有效l Sh

25、ell排序有效地利用了直接插入排序的这两个性质26Shell 排序l算法思想：先将序列转化为若干小序列，在这些小序列内进行插入排序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序，从而完成排序27Shell 排序l l又名：缩小增量排序法又名：缩小增量排序法又名：缩小增量排序法又名：缩小增量排序法(不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价(n n n n1.51.51.51.5)）l ln n n n很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快

26、很小时，或基本有序时排序速度较快28shell排序算法（增量除以2递减）/Modified version of Insertion SortModified version of Insertion Sorttemplate template void void inssort2inssort2(Elem A,(Elem A,intint n,n,intint incrincr)for(for(intint i=i=incrincr;in;i+=;i=(j=incrincr)&()&(Comp:lt(AjComp:lt(Aj,Aj-incrAj-incr););j-=j-=incrincr)

27、swap(A,j,swap(A,j,j-incrj-incr););template template void void shellsortshellsort(Elem(Elem A,A,intint n)n)/ShellsortShellsort for(for(intint i=n/2;i2;i/=2)i=n/2;i2;i/=2)/For each/For each incrincr for(for(intint j=0;ji;j+)j=0;ji;j+)/Sort/Sort sublistssublists inssort2 inssort2(&Aj,n-j,i&Aj,n-j,i););

28、inssort2 inssort2(A,n,1);(A,n,1);29算法分析l 不 稳定l 空间代价：(1)l 时间代价：增量每次除以2递减，则为(n2)选择合适的增量序列，可以使时间代价接近：(n)。30Shell排序增量选择问题l增量每次除以2递减时，效率仍然为(n2)l问题：选取的增量之间并不互质 间距为2k-1的子序列都是由那些间距为2k的子序列组成的 上一轮循环中这些子序列都已经排过序了，导致处理效率不高31l Hibbard增量序列 2k-1，2k-1-1，7，3，1，l Shell(3)和Hibbard增量序列的Shell排序的效率可以达到(n3/2)l 选取其他增量序列还可以

29、更进一步减少时间代价327.4 快速排序l分治法排序：将原始数组分为若干个子部分，然后分别进行排序。l分治策略的实例BST查找、插入、删除算法快速排序、归并排序二分检索l主要思想划分求解子问题(子问题不重叠)综合子问题解，成为问题的解33快速排序算法思想算法思想：l若序列中有n 个元素，任选一个关键字作为轴值，将序列分成两部分。其中左半部分的结点的关键字小于等于轴值，右半部分的结点的关键字大于轴值，然后对左右两部分分别进行类似的处理，直至排好序为止。l关键问题：选择轴值（pivot）将序列划分为两个子序列L和R，使得L中所有记录都小于或等于轴值，R中记录都大于轴值对子序列L和R递归进行快速排序

30、34快速排序示例35轴值选择分割过程l整个快速排序的关键，轴值位于正确位置，分割后使得：L中所有记录位于轴值左边 R中记录位于轴值右边轴值选择l尽可能使L，R长度相等l选择策略：选择最左边记录随机选择选择平均值36一次分割过程l选择轴值并存储轴值l最后一个元素放到轴值位置l初始化下标i,j，分别指向头尾li递增直到遇到比轴值大的元素，将此元素覆盖到j的位置；lj递减直到遇到比轴值小的元素，将此元素覆盖到i的位置l重复上一步直到i=j，将轴值放到i的位置，完毕37快速排序实例 初始序列：初始序列：初始序列：初始序列：72 6 57 88 60 42 83 73 48 8572 6 57 88 6

31、0 42 83 73 48 85轴值轴值6060606060606038快速排序算法（教材（教材 p149-150)p149-150)template template template template void void void void qsortqsortqsortqsort(Elem(Elem(Elem(Elem A,A,A,A,intintintint i,i,i,i,intintintint j)j)j)j)if(j=i)return;if(j=i)return;if(j=i)return;if(j=i)return;/List too smallList too smallL

32、ist too smallList too small，序列元素小于等于，序列元素小于等于，序列元素小于等于，序列元素小于等于1 1 1 1时时时时 intintintint pivotindexpivotindexpivotindexpivotindex=findpivot(Afindpivot(Afindpivot(Afindpivot(A,i,j);,i,j);,i,j);,i,j);swap(A,swap(A,swap(A,swap(A,pivotindexpivotindexpivotindexpivotindex,j);,j);,j);,j);/Put pivot at end/P

33、ut 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 intintintint k=partition k=partition k=partition k=partition(A,i-1,j,Aj);(A,i-1,j,Aj);(A,i-1,

34、j,Aj);(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 qsortqsortqsortqsort (A,i,(A,i,(A,i,(A,i,k-1k-1k-1k-1););););qsortqsortqsortqsort (A,(A,(A,(A,k+1k+1k+1k+1,j);,j);,j);,j);template template template templat

35、e intintintint findpivotfindpivotfindpivotfindpivot(Elem(Elem(Elem(Elem A,A,A,A,intintintint i,i,i,i,intintintint j)j)j)j)/寻找轴值寻找轴值寻找轴值寻找轴值 return(i+j)/2;return(i+j)/2;return(i+j)/2;return(i+j)/2;39快速排序算法（教材（教材 p150)p150)template template template template intintintint partitionpartitionpartitionpar

36、tition(Elem(Elem(Elem(Elem A,A,A,A,intintintint l,l,l,l,intintintint r,Elem&pivot)r,Elem&pivot)r,Elem&pivot)r,Elem&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(while(while(while(Co

37、mp:lt(A+lComp:lt(A+lComp:lt(A+lComp:lt(A+l,pivot);,pivot);,pivot);,pivot);/l/l/l/l右移右移右移右移1 1 1 1位位位位 while(r!=0)&while(r!=0)&while(r!=0)&while(r!=0)&Comp:gt(A-r,pivotComp:gt(A-r,pivotComp:gt(A-r,pivotComp:gt(A-r,pivot););););swap(Aswap(Aswap(Aswap(A,l,r);,l,r);,l,r);,l,r);/Swap out-of-place values/

38、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 las

39、t 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 40轴 值 选 在 最 左41快速排序算法分析（1）n-1k=1l不稳定算法l时间复杂度（交换次数远小于比较次数，主要考虑比较次数）最差情况：轴值总是为当前序列的最小值或者最大值。k=(n2).轴值10，共比较7次轴值20，共比较6次 轴值60，共比较2次轴值70，共

40、比较1次原因：轴值选择不当。改进：随机选取轴值或最左、最右、中间三个元素中的值处于中间的作为轴值，通常可以避免最坏情况。42快速排序算法分析（2）l最佳情况：轴值总是将当前序列均分为2个子序列。共经过logn次分割，故(nlog n)43快速排序算法分析（3）l假设在每次分割时，轴值处于最终排序好的数组中位置的概率是一样的。也就是说，轴值将数组分成长度为0和n-1，1和n-2，的子序列的概率是相等的，都为1/nl长度为n的序列，时间为T(n)，T(0)=T(1)=1，设选择轴值时间为常数l分割时间为cn分割后长度分别为k 和n-1-k对子序列进行快速排序所需时间分别为T(k)和T(n-1-k)

41、l求解递推方程T(n)=cn+1/n*(T(k)+T(n1k)=cn+2/n*T(k)n-1k=0n-1k=044快速排序算法分析（4）l最差情况：时间代价：(n2)空间代价（系统占用堆栈空间代价）系统占用堆栈空间代价）：(n)l最佳情况：时间代价：(nlog n)空间代价：(log n)l平均情况：时间代价：(nlog n)空间代价：(log n)45优化的快速排序可能优化：l轴值选择l小子串不递归子数组小于某个长度（阈值n=9）时，不递归块与块之间有序最后对整个数组进行一次插入排序l消除递归避免进出栈、恢复断点等工作。速度加快。467.5 归并排序算法思想l简单地将原始序列划分为两个子序列

42、l分别对每个子序列递归排序l最后将排好序的子序列合并为一个有序序列，即归并过程477.5 归并排序List List List List mergesort(Listmergesort(Listmergesort(Listmergesort(List inlistinlistinlistinlist)/伪码框架伪码框架伪码框架伪码框架 if(if(if(if(inlist.lengthinlist.lengthinlist.lengthinlist.length()=1)return()=1)return()=1)return()=1)return inlistinlistinlistinli

43、st;List l1=half of the items from List l1=half of the items from List l1=half of the items from List l1=half of the items from inlistinlistinlistinlist;List l2=other half of items from List l2=other half of items from List l2=other half of items from List l2=other half of items from inlistinlistinli

44、stinlist;return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);return merge(mergesort(l1),mergesort(l2);48归并排序算法（教材（教材p154p154）template template template template void void void void mergesortmergesortmergesortmergesort(Elem(Elem(E

45、lem(Elem A,Elem temp,A,Elem temp,A,Elem temp,A,Elem temp,intintintint left,left,left,left,intintintint right)right)right)right)intintintint mid=(left+right)/2;mid=(left+right)/2;mid=(left+right)/2;mid=(left+right)/2;if(left=right)return;if(left=right)return;if(left=right)return;if(left=right)return;

46、/1/1/1/1个元素则返回个元素则返回个元素则返回个元素则返回 mergesortmergesortmergesortmergesort (A,temp,left,(A,temp,left,(A,temp,left,(A,temp,left,midmidmidmid););););mergesortmergesortmergesortmergesort (A,temp,(A,temp,(A,temp,(A,temp,mid+1mid+1mid+1mid+1,right);,right);,right);,right);for(for(for(for(intintintint i=left;i

47、=right;i+)i=left;i=right;i+)i=left;i=right;i+)i=left;i=right;i+)/Copy/Copy/Copy/Copy 子数组子数组子数组子数组 to to to to 临时数组临时数组临时数组临时数组temptemptemptemp tempi=Ai;tempi=Ai;tempi=Ai;tempi=Ai;intintintint i1=left;i1=left;i1=left;i1=left;intintintint i2=mid+1;i2=mid+1;i2=mid+1;i2=mid+1;for(for(for(for(intintintin

48、t currcurrcurrcurr=left;=left;=left;=left;currcurrcurrcurr=right;=right;=right;right)else if(i2 right)else if(i2 right)else if(i2 right)/Right exhausted/Right exhausted/Right exhausted/Right exhausted AcurrAcurrAcurrAcurr=tempi1+;=tempi1+;=tempi1+;=tempi1+;else if(Comp:lt(tempi1,tempi2)else if(Comp:

49、lt(tempi1,tempi2)else if(Comp:lt(tempi1,tempi2)else if(Comp:lt(tempi1,tempi2)AcurrAcurrAcurrAcurr=tempi1+;=tempi1+;=tempi1+;=tempi1+;else else else else AcurrAcurrAcurrAcurr=tempi2+;=tempi2+;=tempi2+;=tempi2+;49优化归并排序l同优化的快速排序一样，对基本已排序序列直接插入排序l归并时从两端开始处理，向中间推进50优化归并排序算法template template template tem

50、plate void void void void mergesortmergesortmergesortmergesort(Elem(Elem(Elem(Elem A,Elem temp,A,Elem temp,A,Elem temp,A,Elem temp,intintintint left,left,left,left,intintintint right)right)right)right)if(right-left)=if(right-left)=if(right-left)=if(right-left)=THRESHOLDTHRESHOLDTHRESHOLDTHRESHOLD)/子