数据结构第7章学习教案.pptx

数据结构数据结构(sh j ji u)第第7章章第一页，共80页。2 27.1 排序排序(pi x)术语及记号术语及记号术语术语术语术语 记录记录记录记录结点结点结点结点 文件文件文件文件线性表线性表线性表线性表 关键码：能够唯一确定结点的一个或若干域。关键码：能够唯一确定结点的一个或若干域。关键码：能够唯一确定结点的一个或若干域。关键码：能够唯一确定结点的一个或若干域。排序码：作为排序运算依据的一个或若干域。排序码：作为排序运算依据的一个或若干域。排序码：作为排序运算依据的一个或若干域。排序码：作为排序运算依据的一个或若干域。组合排序码，组合排序码，组合排序码，组合排序码，(主关键码，次关键码主关键码，次关键码主关键码，次关键码主关键码，次关键码)例，例，例，例，(总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数总分数，数据结构分数，计算引论分数)排序：将一组杂乱无章的数据按一定的规律排序：将一组杂乱无章的数据按一定的规律排序：将一组杂乱无章的数据按一定的规律排序：将一组杂乱无章的数据按一定的规律(gul)(gul)(gul)(gul)排列起来将序列中的记录。排列起来将序列中的记录。排列起来将序列中的记录。排列起来将序列中的记录。第1页/共80页第二页，共80页。3 3术语(shy)排序问题排序问题给定一组记录序列给定一组记录序列R=r1,r2,.rn,R=r1,r2,.rn,其排序码分别为其排序码分别为K=k1,k2,K=k1,k2,，kn kn 将这些记录排成顺序为将这些记录排成顺序为R=R=rs1,rs2,rs1,rs2,，rsn rsn 的一个序列的一个序列S S，其排序码序列其排序码序列K=ks1K=ks1，ks2ks2，ksn ksn 是一个满足某种关系的是一个满足某种关系的有序序列。关系是任意有序序列。关系是任意(rny)(rny)的，的，如通常经常使用的小于、大于等关如通常经常使用的小于、大于等关系或任意系或任意(rny)(rny)的关系。的关系。第2页/共80页第三页，共80页。4 4术语(shy)内排序内排序内排序内排序全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。外排序外排序外排序外排序排序过程排序过程排序过程排序过程(guchng)(guchng)(guchng)(guchng)还要访问外存还要访问外存还要访问外存还要访问外存(因为待因为待因为待因为待排记录的数量太大，内存容纳不下排记录的数量太大，内存容纳不下排记录的数量太大，内存容纳不下排记录的数量太大，内存容纳不下)排序算法的稳定排序算法的稳定排序算法的稳定排序算法的稳定&不稳定不稳定不稳定不稳定如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象riririri和和和和rjrjrjrj，它们的关，它们的关，它们的关，它们的关键码键码键码键码 ki=kj ki=kj ki=kj ki=kj，且在排序之前，对象，且在排序之前，对象，且在排序之前，对象，且在排序之前，对象riririri排在排在排在排在rjrjrjrj前面。如果在排序之后，对象前面。如果在排序之后，对象前面。如果在排序之后，对象前面。如果在排序之后，对象riririri仍在对象仍在对象仍在对象仍在对象rjrjrjrj的前面，则称这个排序方法是稳定的，否则称这个排的前面，则称这个排序方法是稳定的，否则称这个排的前面，则称这个排序方法是稳定的，否则称这个排的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。序方法是不稳定的。序方法是不稳定的。序方法是不稳定的。第3页/共80页第四页，共80页。5 5基本操作 按排序依据原则按排序依据原则按排序依据原则按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔插入排序：直接插入排序、折半插入排序、希尔插入排序：直接插入排序、折半插入排序、希尔插入排序：直接插入排序、折半插入排序、希尔（shellshellshellshell）排序）排序）排序）排序 交换排序：冒泡排序、快速交换排序：冒泡排序、快速交换排序：冒泡排序、快速交换排序：冒泡排序、快速(kui s)(kui s)(kui s)(kui s)排序排序排序排序 选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序选择排序：简单选择排序、堆排序 归并排序：归并排序：归并排序：归并排序：2-2-2-2-路归并排序路归并排序路归并排序路归并排序 基数排序基数排序基数排序基数排序第4页/共80页第五页，共80页。6 67.2 三种代价三种代价(diji)为为O(n2)的排序方法的排序方法7.2.1 7.2.1 插入排序插入排序7.2.2 7.2.2 冒泡排序冒泡排序7.2.3 7.2.3 选择选择(xunz)(xunz)排序排序第5页/共80页第六页，共80页。7 77.2.1 7.2.1 插入排序插入排序算法思想：逐个处理待排序的记录，每个记录都要与前面(qin mian)那些已排好序的记录进行比较，然后插入到适当的位置。第6页/共80页第七页，共80页。8 87.2.1 教材教材(jioci)上插入排序算上插入排序算法法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);算法分析：算法分析：算法分析：算法分析：稳定稳定稳定稳定空间代价空间代价空间代价空间代价(diji)(diji)(diji)(diji)：(1)(1)(1)(1)时间代价时间代价时间代价时间代价(diji)(diji)(diji)(diji)：最佳情况：最佳情况：最佳情况：最佳情况：n-1n-1n-1n-1次比较，次比较，次比较，次比较，0 0 0 0次交换，次交换，次交换，次交换，(n)(n)(n)(n)最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为最差情况：比较次数为i=n(n-1)/2=(n2)i=n(n-1)/2=(n2)i=n(n-1)/2=(n2)i=n(n-1)/2=(n2)交换次数为交换次数为交换次数为交换次数为 3i=3n(n-1)/2=(n2)3i=3n(n-1)/2=(n2)3i=3n(n-1)/2=(n2)3i=3n(n-1)/2=(n2)（一次（一次（一次（一次swapswapswapswap需要交换需要交换需要交换需要交换3 3 3 3次）次）次）次）平均情况：平均情况：平均情况：平均情况：(n2)(n2)(n2)(n2)i=1n-1i=1n-1第7页/共80页第八页，共80页。9 9改进(gijn)的插入排序算法template class Elem,class template Compvoid inssort(Elem A,int n)void inssort(Elem A,int n)for(int i=1;in;i+)for(int i=1;i=0 while(j=0&(Comp:lt(temp,Aj)&(Comp:lt(temp,Aj)Aj+1=Aj;j-;/Aj+1=Aj;j-;/将将=Ai=Ai的记录后移的记录后移 Aj+1=temp;/Aj+1 Aj+1=temp;/Aj+1是记是记录录AiAi的正确的正确(zhngqu)(zhngqu)位置位置 第8页/共80页第九页，共80页。1010改进插入排序算法(sun f)分析算法分析：算法分析：稳定稳定空间代价：空间代价：(1)(1)时间代价：时间代价：最佳情况：最佳情况：n-1n-1次比较，次比较，n n次交换次交换(jiohun)(jiohun)，(n)(n)最差情况：比较次数为最差情况：比较次数为(n2)(n2)（同前）（同前）交换交换(jiohun)(jiohun)次数为次数为 i=n(n-1)/2=(n2)i=n(n-1)/2=(n2)平均情况：平均情况：(n2)(n2)i=1n-1第9页/共80页第十页，共80页。1111加入(jir)监视哨的插入排序算法template class Elem,class template Compvoid 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+)A0=Ai;/A0=Ai;/数组有效数组有效(yuxio)(yuxio)存储从存储从A1A1开始开始 j=i-1;j=i-1;while(Comp:lt(A0,while(Comp:lt(A0,Aj)Aj)Aj+1=Aj;j-;Aj+1=Aj;j-;Aj+1=A0;Aj+1=A0;第10页/共80页第十一页，共80页。1212利用(lyng)二分法的插入排序思想：在插入第i个记录时，前面的记录已经有序。故可以用二分法查找(ch zho)第i个记录的正确位置。第11页/共80页第十二页，共80页。13137.2.2 起泡(q po)排序算法思想：若序列中有n 个元素，通常进行n-1 趟。第1 趟，针对第Vector0 至Vectorn-1个元素进行。第2 趟，针对第Vector1至Vectorn-1 个元素进行第n-1 趟，针对第Vectorn-2至Vectorn-1 个元素进行。每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确(zhngqu)，则进行交换；否则继续比较下面两个相邻的元素。第12页/共80页第十三页，共80页。14147.2.2 起泡(q po)排序不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到(zhdo)所有的记录都已经排好序。第13页/共80页第十四页，共80页。1515教材上起泡(q po)排序算法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页第十五页，共80页。1616起泡排序算法(sun f)分析 稳定 空间代价：(1)（此章我们仅分析排序所需额外空间开销）时间代价：比较次数：最佳(zu ji)、最差i=n(n-1)/2=(n2)交换次数最多为(n2)，最少为0，平均为(n2)。最大，最小，平均时间代价均为(n2)。1i=n-1第15页/共80页第十六页，共80页。1717优化的起泡(q po)算法改进：检查每次起泡过程(guchng)中是否发生过交换，如果没有，则表明整个数组已经排好序，排序结束。避免不必要的比较。第16页/共80页第十七页，共80页。1818改进的起泡(q po)排序算法template class Elem,class template Compvoid bubsort(Elem A,int n)void bubsort(Elem A,int n)int int flagflag;for(int i=0;in-1;i+)for(int i=0;ii;j-)for(int j=n-1;ji;j-)if(Comp:lt(Aj,Aj-if(Comp:lt(Aj,Aj-1)1)swap(A,j,j-swap(A,j,j-1);1);flag=TRUEflag=TRUE;if(if(flag=FALSEflag=FALSE)return;)return;第17页/共80页第十八页，共80页。1919优化起泡(q po)排序算法分析算法分析：算法分析：稳定稳定时间代价：时间代价：最佳情况最佳情况(qngkung)(qngkung)：n-1n-1次比较，次比较，0 0次交换，次交换，(n)(n)最差情况最差情况(qngkung)(qngkung)：比较和交：比较和交换次数均为换次数均为(n2)(n2)平均情况平均情况(qngkung)(qngkung)：(n2)(n2)第18页/共80页第十九页，共80页。20207.2.3 直接(zhji)选择排序算法思想：找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，比起泡排序减少了移动(ydng)次数。第19页/共80页第二十页，共80页。2121直接选择排序(pi x)算法template class Elem,class template Compvoid selsort(Elem A,int n)void selsort(Elem A,int n)for(int i=0;in-1;i+)for(int i=0;ii;j-)for(int j=n-1;ji;j-)/Find leastFind least if(Comp:lt(Aj,if(Comp:lt(Aj,Alowindex)Alowindex)lowindex=jlowindex=j;/Put/Put it in placeit in place swap(A,i,swap(A,i,lowindexlowindex););第20页/共80页第二十一页，共80页。2222算法(sun f)分析 不 稳定 空间代价：(1)时间(shjin)代价：比较次数：最好、最坏情况均为(n-i-1)=n*(n-1)/2，即(n2)交换次数：最好（自身交换）、最坏3(n-1)（一次swap需要交换3次），故(n)总时间(shjin)代价：(n2)。i=0n-2第21页/共80页第二十二页，共80页。2323交换指针(zhzhn)，减少交换记录的次数第22页/共80页第二十三页，共80页。2424小结：时间(shjin)代价第23页/共80页第二十四页，共80页。2525小结(xioji)：时间代价（2）时间复杂度为(n2)的原因：一个长度为n序列平均有n(n-1)/4对逆置任何一种(y zhn)只对相邻记录进行比较的排序算法的平均时间代价都是(n2)第24页/共80页第二十五页，共80页。26267.3 Shell 排序(pi x)（希尔排序(pi x)）直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价(diji)为(n)对于短序列，直接插入排序比较有效 Shell排序有效地利用了直接插入排序的这两个性质第25页/共80页第二十六页，共80页。2727Shell 排序(pi x)算法思想：先将序列转化(zhunhu)为若干小序列，在这些小序列内进行插入排序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序，从而完成排序第26页/共80页第二十七页，共80页。2828Shell 排序(pi x)又名：缩小增量又名：缩小增量又名：缩小增量又名：缩小增量(zn lin)(zn lin)(zn lin)(zn lin)排序法排序法排序法排序法(不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价不稳定算法，时间代价(n1.5)(n1.5)(n1.5)(n1.5)）n n n n很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快很小时，或基本有序时排序速度较快第27页/共80页第二十八页，共80页。2929shell排序算法(sun f)（增量除以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页第二十九页，共80页。3030算法(sun f)分析 不 稳定 空间代价：(1)时间代价：增量每次除以2递减，则为(n2)选择合适(hsh)的增量序列，可以使时间代价接近：(n)。第29页/共80页第三十页，共80页。3131Shell排序增量选择(xunz)问题增量每次除以2递减时，效率仍然为(n2)问题：选取的增量之间并不互质 间距为2k-1的子序列都是由那些间距为2k的子序列组成(z chn)的 上一轮循环中这些子序列都已经排过序了，导致处理效率不高第30页/共80页第三十一页，共80页。3232 Hibbard增量序列 2k-1，2k-1-1，7，3，1，Shell(3)和Hibbard增量序列的Shell排序的效率(xio l)可以达到(n3/2)选取其他增量序列还可以更进一步减少时间代价第31页/共80页第三十二页，共80页。33337.4 快速(kui s)排序分治法排序：将原始数组分为若干个子部分，然后分别分治法排序：将原始数组分为若干个子部分，然后分别(fnbi)(fnbi)进行排序。进行排序。分治策略的实例分治策略的实例BSTBST查找、插入、删除算法查找、插入、删除算法快速排序、归并排序快速排序、归并排序二分检索二分检索主要思想主要思想划分划分求解子问题求解子问题(子问题不重叠子问题不重叠)综合子问题解，成为问题的解综合子问题解，成为问题的解第32页/共80页第三十三页，共80页。3434快速排序(pi x)算法思想算法思想：算法思想：若序列中有若序列中有n n 个元素，任选一个关键字作为轴值，将序列分成两部分。其中左半部分的结个元素，任选一个关键字作为轴值，将序列分成两部分。其中左半部分的结点的关键字小于等于轴值，右半部分的结点的关键字大于轴值，然后对左右两部分点的关键字小于等于轴值，右半部分的结点的关键字大于轴值，然后对左右两部分分别进行类似的处理，直至排好序为止。分别进行类似的处理，直至排好序为止。关键问题：关键问题：选择轴值（选择轴值（pivotpivot）将序列划分为两个将序列划分为两个(lin)(lin)子序列子序列L L和和R R，使得，使得L L中所有记录都小于或等于轴值，中所有记录都小于或等于轴值，R R中记中记录都大于轴值录都大于轴值对子序列对子序列L L和和R R递归进行快速排序递归进行快速排序第33页/共80页第三十四页，共80页。3535快速排序(pi x)示例第34页/共80页第三十五页，共80页。3636轴值选择(xunz)分割分割(fng)(fng)过程过程整个快速排序的关键，轴值位于正确位置，分割整个快速排序的关键，轴值位于正确位置，分割(fng)(fng)后使得：后使得：L L中所有记录位于轴值左边中所有记录位于轴值左边 R R中记录位于轴值右边中记录位于轴值右边轴值选择轴值选择尽可能使尽可能使L L，R R长度相等长度相等选择策略：选择策略：选择最左边记录选择最左边记录随机选择随机选择选择平均值选择平均值第35页/共80页第三十六页，共80页。3737一次分割(fng)过程选择轴值并存储轴值最后一个元素放到轴值位置初始化下标i,j，分别指向头尾i递增直到遇到(y do)比轴值大的元素，将此元素覆盖到j的位置；j递减直到遇到(y do)比轴值小的元素，将此元素覆盖到i的位置重复上一步直到i=j，将轴值放到i的位置，完毕第36页/共80页第三十七页，共80页。3838快速(kui s)排序实例 初始初始初始初始(ch sh)(ch sh)序列：序列：序列：序列：72 6 57 88 60 42 83 73 48 85 72 6 57 88 60 42 83 73 48 85轴值轴值60606060606060第37页/共80页第三十八页，共80页。3939快速排序(pi x)算法（教材 p149-150)template template template template void qsort(Elem A,int i,int j)void qsort(Elem A,int i,int j)void qsort(Elem A,int i,int j)void qsort(Elem A,int i,int j)if(j=i)return;if(j=i)return;if(j=i)return;if(j=i)return;/List too small/List too small/List too small/List too small，序列元素，序列元素，序列元素，序列元素小于等于小于等于小于等于小于等于(dngy)1(dngy)1(dngy)1(dngy)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,k-1);qsort(A,i,k-1);qsort(A,i,k-1);qsort(A,i,k-1);qsort(A,k+1,j);qsort(A,k+1,j);qsort(A,k+1,j);qsort(A,k+1,j);template template template template int findpivot(Elem A,int i,int j)/int findpivot(Elem A,int i,int j)/int findpivot(Elem A,int i,int j)/int findpivot(Elem A,int i,int j)/寻找轴值寻找轴值寻找轴值寻找轴值 return(i+j)/2;return(i+j)/2;return(i+j)/2;return(i+j)/2;第38页/共80页第三十九页，共80页。4040快速排序算法(sun f)（教材 p150)template template template template int partition(Elem A,int l,int r,Elem&pivot)int partition(Elem A,int l,int r,Elem&pivot)int partition(Elem A,int l,int r,Elem&pivot)int partition(Elem A,int l,int r,Elem&pivot)do /Move the bounds in until they meet do /Move the bounds in until they meet do /Move the bounds in until they meet do /Move the bounds in until they meet while(Comp:lt(A+l,pivot);/l while(Comp:lt(A+l,pivot);/l while(Comp:lt(A+l,pivot);/l while(Comp:lt(A+l,pivot);/l右移右移右移右移(yu y)1(yu y)1(yu y)1(yu y)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 out-of-place values swap(A,l,r);/Swap out-of-place values swap(A,l,r);/Swap out-of-place values swap(A,l,r);/Swap out-of-place values while(l r);/Stop when they cross while(l r);/Stop when they cross while(l r);/Stop when they cross while(l r);/Stop when they cross swap(A,l,r);/Reverse last swap swap(A,l,r);/Reverse last swap swap(A,l,r);/Reverse last swap swap(A,l,r);/Reverse last swap return l;/Return first pos on right return l;/Return first pos on right return l;/Return first pos on right return l;/Return first pos on right 第39页/共80页第四十页，共80页。4141轴 值 选 在 最 左第40页/共80页第四十一页，共80页。4242快速排序算法(sun f)分析（1）n-1k=1不稳定算法时间复杂度（交换次数远小于比较次数，主要考虑比较次数）最差情况(qngkung)：轴值总是为当前序列的最小值或者最大值。k=(n2).轴值10，共比较(bjio)7次轴值20，共比较(bjio)6次 轴值60，共比较(bjio)2次轴值70，共比较(bjio)1次原因：轴值选择不当。改进：随机选取轴值或最左、最右、中间三个元素中的值处于中间的作为轴值，通常可以避免最坏情况。第41页/共80页第四十二页，共80页。4343快速(kui s)排序算法分析（2）最佳情况：轴值总是将当前(dngqin)序列均分为2个子序列。共经过logn次分割，故(nlog n)第42页/共80页第四十三页，共80页。4444快速排序算法(sun f)分析（3）假设在每次分割时，轴值处于最终排序假设在每次分割时，轴值处于最终排序(pi x)(pi x)好的数组好的数组中位置的概率是一样的。中位置的概率是一样的。也就是说，轴值将数组分成长也就是说，轴值将数组分成长度为度为0 0和和n-1n-1，1 1和和n-2n-2，的子序列的概率是相等的，都的子序列的概率是相等的，都为为1/n1/n长度为长度为n n的序列，时间为的序列，时间为T(n)T(n)，T(0)=T(1)=1T(0)=T(1)=1，设选择，设选择轴值时间为常数轴值时间为常数分割时间为分割时间为cncn分割后长度分别为分割后长度分别为k k 和和n-1-kn-1-k对子序列进行快速排序对子序列进行快速排序(pi x)(pi x)所需时间分别为所需时间分别为T(k)T(k)和和T(n-1-k)T(n-1-k)求解递推方程求解递推方程T(n)=cn+1/n*(T(k)+T(n1k)=cn+2/n*T(k)T(n)=cn+1/n*(T(k)+T(n1k)=cn+2/n*T(k)n-1k=0n-1k=0第43页/共80页第四十四页，共80页。4545快速排序算法(sun f)分析（4）最差情况：时间(shjin)代价：(n2)空间代价（系统占用堆栈空间代价）：(n)最佳情况：时间(shjin)代价：(nlog n)空间代价：(log n)平均情况：时间(shjin)代价：(nlog n)空间代价：(log n)第44页/共80页第四十五页，共80页。4646优化的快速(kui s)排序可能优化：轴值选择小子串不递归子数组小于某个长度（阈值n=9）时，不递归块与块之间有序最后对整个数组进行一次插入排序消除递归避免(bmin)进出栈、恢复断点等工作。速度加快。第45页/共80页第四十六页，共80页。47477.5 归并(gubng)排序算法思想简单地将原始序列划分为两个子序列分别(fnbi)对每个子序列递归排序最后将排好序的子序列合并为一个有序序列，即归并过程第46页/共80页第四十七页，共80页。48487.5 归并(gubng)排序List mergesort(List inlist)/List mergesort(List inlist)/List mergesort(List inlist)/List mergesort(List inlist)/伪码框架伪码框架伪码框架伪码框架(kun ji)(kun ji)(kun ji)(kun ji)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页第四十八页，共80页。4949归并排序(pi x)算法（教材p154）template template template template void mergesort(Elem A,Elem temp,int left,int right)void mergesort(Elem A,Elem temp,int left,int right)void mergesort(Elem A,Elem temp,int left,int right)void mergesort(Elem A,Elem temp,int left,int 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个元素则返回个元素则返回个元素则返回个元素则返回(fnhu)(fnhu)(fnhu)(fnhu)mergesort(A,temp,left,mid);mergesort(A,temp,left,mid);mergesort(A,temp,left,mid);mergesort(A,temp,left,mid);mergesort(A,temp,mid+1,right);mergesort(A,temp,mid+1,right);mergesort(A,temp,mid+1,right);mergesort(A,temp,mid+1,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 子数组子数组子数组子数组 totototo 临时数组临时数组临时数组临时数组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=