数据结构第7章学习教案.pptx
《数据结构第7章学习教案.pptx》由会员分享,可在线阅读,更多相关《数据结构第7章学习教案.pptx(80页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构数据结构(sh j ji u)第第7章章第一页,共80页。2 27.1 排序排序(pi x)术语及记号术语及记号术语术语术语术语 记录记录记录记录结点结点结点结点 文件文件文件文件线性表线性表线性表线性表 关键码:能够唯一确定结点的一个或若干域。关键码:能够唯一确定结点的一个或若干域。关键码:能够唯一确定结点的一个或若干域。关键码:能够唯一确定结点的一个或若干域。排序码:作为排序运算依据的一个或若干域。排序码:作为排序运算依据的一个或若干域。排序码:作为排序运算依据的一个或若干域。排序码:作为排序运算依据的一个或若干域。组合排序码,组合排序码,组合排序码,组合排序码,(主关键码,次关键
2、码主关键码,次关键码主关键码,次关键码主关键码,次关键码)例,例,例,例,(总分数,数据结构分数,计算引论分数总分数,数据结构分数,计算引论分数总分数,数据结构分数,计算引论分数总分数,数据结构分数,计算引论分数)排序:将一组杂乱无章的数据按一定的规律排序:将一组杂乱无章的数据按一定的规律排序:将一组杂乱无章的数据按一定的规律排序:将一组杂乱无章的数据按一定的规律(gul)(gul)(gul)(gul)排列起来将序列中的记录。排列起来将序列中的记录。排列起来将序列中的记录。排列起来将序列中的记录。第1页/共80页第二页,共80页。3 3术语(shy)排序问题排序问题给定一组记录序列给定一组记录
3、序列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
4、)内排序内排序内排序内排序全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。全部记录都可以同时调入内存进行的排序。外排序外排序外排序外排序排序过程排序过程排序过程排序过程(guchng)(guchng)(guchng)(guchng)还要访问外存还要访问外存还要访问外存还要访问外存(因为待因为待因为待因为待排记录的数量太大,内存容纳不下排记录的数量太大,内存容纳不下排记录的数量太大,内存容纳不下排记录的数量太大,内存容纳不下)排序算法的稳定排序算法的稳定排序算法的稳定排序算法的稳定&不稳定不稳定不稳定不稳定如果在对象序列中有两个对
5、象如果在对象序列中有两个对象如果在对象序列中有两个对象如果在对象序列中有两个对象riririri和和和和rjrjrjrj,它们的关,它们的关,它们的关,它们的关键码键码键码键码 ki=kj ki=kj ki=kj ki=kj,且在排序之前,对象,且在排序之前,对象,且在排序之前,对象,且在排序之前,对象riririri排在排在排在排在rjrjrjrj前面。如果在排序之后,对象前面。如果在排序之后,对象前面。如果在排序之后,对象前面。如果在排序之后,对象riririri仍在对象仍在对象仍在对象仍在对象rjrjrjrj的前面,则称这个排序方法是稳定的,否则称这个排的前面,则称这个排序方法是稳定的,
6、否则称这个排的前面,则称这个排序方法是稳定的,否则称这个排的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。序方法是不稳定的。序方法是不稳定的。序方法是不稳定的。第3页/共80页第四页,共80页。5 5基本操作 按排序依据原则按排序依据原则按排序依据原则按排序依据原则 插入排序:直接插入排序、折半插入排序、希尔插入排序:直接插入排序、折半插入排序、希尔插入排序:直接插入排序、折半插入排序、希尔插入排序:直接插入排序、折半插入排序、希尔(shellshellshellshell)排序)排序)排序)排序 交换排序:冒泡排序、快速交换排序:冒泡排序、快速交换排序:冒泡排序、快速交换排序
7、:冒泡排序、快速(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
8、页/共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
9、;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)
10、(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
11、-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(i
12、nt 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
13、)最差情况:比较次数为最差情况:比较次数为(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;/数
14、组有效数组有效(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 至Ve
15、ctorn-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 tem
16、plate 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-
17、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)中是否发生过交换,如果没
18、有,则表明整个数组已经排好序,排序结束。避免不必要的比较。第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);f
19、lag=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 直
20、接(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
21、(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页。23
22、23交换指针(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排序有效
23、地利用了直接插入排序的这两个性质第25页/共80页第二十六页,共80页。2727Shell 排序(pi x)算法思想:先将序列转化(zhunhu)为若干小序列,在这些小序列内进行插入排序逐渐扩大小序列的规模,而减少小序列个数,使得待排序序列逐渐处于更有序的状态最后对整个序列进行扫尾直接插入排序,从而完成排序第26页/共80页第二十七页,共80页。2828Shell 排序(pi x)又名:缩小增量又名:缩小增量又名:缩小增量又名:缩小增量(zn lin)(zn lin)(zn lin)(zn lin)排序法排序法排序法排序法(不稳定算法,时间代价不稳定算法,时间代价不稳定算法,时间代价不稳定算法
24、,时间代价(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,
25、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)/F
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 学习 教案
限制150内