数据结构排序选择排序归并排序基数排序学习教案.pptx

《数据结构排序选择排序归并排序基数排序学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构排序选择排序归并排序基数排序学习教案.pptx（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构排序数据结构排序(pi x)选择排序选择排序(pi x)归并排序归并排序(pi x)基数排序基数排序(pi x)第一页，共70页。第第1010章章 内部内部(nib)(nib)排序排序选择(xunz)排序(直接排序、堆排序)概述(ish)插入排序(直接排序、折半排序、希尔排序)交换排序(冒泡排序、快速排序)归并排序基数排序第1页/共70页第二页，共70页。v选择(xunz)排序10.4 选择选择(xunz)排排序序基本思想：第i趟在n-i+1(i=1,2,n-1)个记录中选取(xunq)关键字最小的记录作为有序序列中的第i个记录。1.简单选择排序2.树形选择排序3.堆排序第2页

2、/共70页第三页，共70页。v简单选择(xunz)排序10.4 选择选择(xunz)排排序序排序过程：首先(shuxin)通过n1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n2次比较，从剩余的n1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n1趟排序后，排序结束。第3页/共70页第四页，共70页。v简单(jindn)选择排序10.4 选择选择(xunz)排排序序例：初始(chsh)：49386597761327jjjjjjki=11349一趟：13386597764927i=2二趟：13276597764938三趟：13273897

3、764965四趟：13273849769765五趟：13273849659776六趟：13273849657697排序结束：六趟：13273849657697kki=6i=3i=4i=5比较次数n-1n-2n-6第4页/共70页第五页，共70页。v简单选择排序(pix)算法描述10.4 选择选择(xunz)排排序序voidSelectSort(SqList&L)/对顺序表L作简单(jindn)选择排序for(i=1;iL.length;+i)k=i;for(j=i+1;j=n;j+)if(L.rj.keyL.rk.key)k=j;if(i!=k)L.riL.rk;/与第i个记录交换/Selec

4、tSort第5页/共70页第六页，共70页。v简单选择排序算法(sunf)分析10.4 选择选择(xunz)排排序序由于存在着不相邻元素之间的互换，因此，简单选择排序(pix)是“不稳定的”。算法实现共需要进行n-1次选择，每次选择需要进行n-i次比较(1in-1)，而每次交换最多需3次移动，因此，总的比较次数C=n(n-1)/2，总的移动次数M=3(n-1)。故其时间复杂度为O(n2)。空间效率：O(1)交换时用到一个暂存单元第6页/共70页第七页，共70页。v树形选择(xunz)排序(又称锦标赛排序)10.4 选择选择(xunz)排排序序基本思想：与体育比赛时的淘汰赛类似。首先对n个记录的

5、关键字进行两两比较(bjio)，得到n/2个优胜者(关键字小者)，作为第一步比较(bjio)的结果保留下来。然后在这n/2个较小者之间再进行两两比较(bjio)，如此重复，直到选出最小关键字的记录为止。例：关键字序列T=（21，25，49，25*，16，08，63），请给出锦标赛排序的具体实现过程。第7页/共70页第八页，共70页。08Winner(胜者)2108086325*2121254925*160863r1注：为便于自动处理，建议每个记录多开两个(lin)特殊分量：keyotherinfoIndex(结点位置编号）结点位置编号）Tag（是否参加比较）（是否参加比较）初态补足2k(k=l

6、og2n)个叶子(yzi)结点第一趟：第一趟：Tree8Tree9Tree10Tree11Tree12Tree13Tree14Tree15第8页/共70页第九页，共70页。第二趟：第二趟：082108086325*2121254925*160863161616r2Winner(胜者)求次小值16时,只需比较(bjio)2次，即只比较(bjio)log2n-1次。令其Tag0,不参与(cny)比较第9页/共70页第十页，共70页。令其Tag0,不参与(cny)比较第三第三(d(d sn)sn)趟：趟：162116166325*2121254925*160863r3Winner(胜者)6321第1

7、0页/共70页第十一页，共70页。082108086325*2121254925*1608636321第四趟：第四趟：r4Winner(胜者)252525第11页/共70页第十二页，共70页。082108086325*2121254925*1608631616166321252525第五第五(d(d w w)趟：趟：r5Winner(胜者)25*25*第12页/共70页第十三页，共70页。082108086325*2121254925*160863161616632125252525*25*第六趟：第六趟：r6Winner(胜者)494949第13页/共70页第十四页，共70页。0821080

8、86325*2121254925*160863161616632125252525*25*494949第七趟：第七趟：r7Winner(胜者)63第14页/共70页第十五页，共70页。v树形选择排序(pix)算法10.4 选择选择(xunz)排排序序胜者树数据(shj)结点类的定义DataNodeTypedata;/数据值intindex;/结点在满二叉树中顺序号intactive;/参选标志：=1,参选,=0,不参选第15页/共70页第十六页，共70页。锦标赛排序的算法voidTournamentSort(Typea,intn)intbottomRowSize=PowerOfTwo(n);/

9、乘幂值计算满足n的2的最小次幂的数intTreeSize=2*bottomRowSize-1;/总结点个数intloadindex=bottomRowSize-1;/内结点个数DataNodetreeTreeSize;intj=0;/从a向胜者树外结点复制数据for(inti=loadindex;iTreeSize;i+)treei.index=i;if(jn)treei.active=1;treei.data=aj+;elsetreei.active=0;i=loadindex;/进行初始比较选择最小的项while(i)j=i;while(j2*i)if(!treej+1.active|tr

10、eej.datatreej+1.data)/胜者送入双亲(shungqn)tree(j-1)/2=treej;elsetree(j-1)/2=treej+1;j+=2;i=(i-1)/2;/i退到双亲(shungqn),直到i=0为止for(i=0;in-1;i+)/处理其它n-1个数据ai=tree0.data;/送出最小数据treetree0.index.active=0;/失去(shq)参选资格UpdateTree(tree,tree0.index);/调整an-1=tree0.data;/TournamentSort第16页/共70页第十七页，共70页。锦标赛排序中的调整算法voidU

11、pdateTree(DataNode*tree,inti)if(i%2=0)tree(i-1)/2=treei-1;/i偶数(ush),对手左结点elsetree(i-1)/2=treei+1;/i奇数,对手右结点i=(i-1)/2;/向上调整while(i)/直到i=0if(i%2=0)j=i-1;elsej=i+1;if(!treei.active|!treej.active)if(treei.active)tree(i-1)/2=treei;/i可参选,i上elsetree(i-1)/2=treej;/否则,j上else/两方都可参选if(treei.datatreej.data)tre

12、e(i-1)/2=treei;/关键码小者上elsetree(i-1)/2=treej;i=(i-1)/2;/i上升到双亲第17页/共70页第十八页，共70页。v树形选择排序算法(sunf)分析10.4 选择选择(xunz)排排序序锦标赛排序构成的树是满(完全)二叉树，其深度为log2n+1，其中(qzhng)n为待排序元素个数。时间复杂度：O(nlog2n)n个记录各自比较约log2n次空间效率：O(n)胜者树的附加内结点共有n-1个！稳定性：稳定左右结点相同者左为先n=2k=叶子总数第18页/共70页第十九页，共70页。v堆排序10.4 选择选择(xunz)排排序序1.什么(shnme)是

13、堆？堆的定义：设有n个元素的序列(xli)k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。kik2ikik2i+1ki k2ikik2i+1或者i=1,2,n/22.怎样建堆？3.怎样堆排序？解释：如果让满足以上条件的元素序列(k1，k2，kn)顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于(或小于)其左右孩子，此树的根结点(即堆顶)必最大(或最小)。第19页/共70页第二十页，共70页。v堆排序10.4 选择选择(xunz)排排序序082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,6

14、7）和序列T2=（91,85,76,66,58,67,55）,判断它们(tmen)是否“堆”？（小根堆）（小顶堆）（最小堆）（大顶堆）（最大堆）第20页/共70页第二十一页，共70页。v怎样(znyng)建堆？10.4 选择选择(xunz)排排序序将排序码k1,k2,k3,kn表示成一棵完全二叉树，然后从第n/2个排序码（即最右边的非终端结点）开始筛选，使由该结点作为根结点组成(zchn)的子二叉树符合堆的定义，然后从第n/2-1个排序码重复刚才操作，直到第一个排序码（即根）止。这时候，该二叉树符合堆的定义，初始堆已经建立。第21页/共70页第二十二页，共70页。v怎样(znyng)建堆？10

15、.4 选择选择(xunz)排排序序212525491608123456例：关键字序列(xli)T=(21，25，49，25，16，08），请建大根堆为便于理解，先将原始序列画成完全二叉树的形式21i=3:49而且21还应当向下比较！i=1:21小于25和49，要调整！49大于08，不必调整；i=2:25大于等于25和16，不必调整；完全二叉树的最右一个非终端结点编号必为n/2！(性质5)注：终端结点（即叶子）没有任何子女，无需单独调整。第22页/共70页第二十三页，共70页。v怎样(znyng)建堆？10.4 选择选择(xunz)排排序序这个(zhge)自堆顶至叶子的调整过程称为“筛选”。筛选

16、:假若完全二叉树的某一个结点i，它的左、右子树已是堆。需要将R2i.key与R2i+1.key之中的最小者与Ri.key比较，若Ri.key较大则交换，这有可能破坏下一级堆。于是继续采用上述方法构造下一级堆，直到完全二叉树中结点i构成堆为止。第23页/共70页第二十四页，共70页。v怎样(znyng)建堆？10.4 选择选择(xunz)排排序序第24页/共70页第二十五页，共70页。v怎样(znyng)建堆？10.4 选择选择(xunz)排排序序voidHeapAdjust(SqListH，ints，intm)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数调整H

17、.rs的关键字，使H.rs.m成为一个大顶堆rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选,j为key较大的记录的下标if(j0;-i)/把H.r1.length建成大顶堆HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)/将堆顶记录和当前(dngqin)未经排/序子序列H.r.1.i中最后一个记录相互交换H.r1H.ri；HeapAdjust(H,1,i-1);/将H.R1.i-1重新调整为大顶堆/HeapSort第32页/共70页第三十三页，共70页。v附1：基于初始堆进行堆排序的算法(sunf)步骤10.4

18、 选择选择(xunz)排排序序1.堆的第一个对象V0具有最大的关键码，将V0与Vn对调，把具有最大关键码的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果(jigu)具有次最大关键码的对象又上浮到堆顶，即V0位置。2.再对调V0和Vn-1，调用对前n-2个对象重新调整，如此反复，最后得到全部排序好的对象序列。第33页/共70页第三十四页，共70页。rc=H.rs;j=2s;jm&H.rj.keyH.rj+1.key+j;/指向右兄弟jH.rj.keyH.rs=H.rj;s=j;j=2*j;/指向左孩子NNNYYYH.rsm中除rs外，其他具有堆特征现调整rs的值，使H

19、.rsm为堆附附2 2：算法算法(sunf)(sunf)流程流程比较左右孩子大小(dxio)，j指向大者比较(bjio)大孩子与rc的大小若大向上浮第34页/共70页第三十五页，共70页。v堆排序的效率(xiol)分析10.4 选择选择(xunz)排排序序在整个堆排序中，共需要进行n+n/2-1次筛选运算(ynsun)，每次筛选运算(ynsun)进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度。故每次筛选运算(ynsun)的时间复杂度为O(log2n)，则整个堆排序过程的时间复杂度为O(nlog2n)。堆排序在最坏情况下，时间复杂度也为O(nlog2n)。相对于快速排

20、序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换使用。由于存在着不相邻元素之间的互换，因此，堆排序是一种不稳定的排序方法。第35页/共70页第三十六页，共70页。v堆排序的效率(xiol)分析10.4 选择选择(xunz)排排序序时间效率：O(nlog2n)。因为整个排序过程(guchng)中需要调用n-1次HeapAdjust()算法，HeapAdjust()而算法本身耗时为log2n；空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。稳定性：不稳定。优点：对少量数据效果不明显，但对大量数据有效。第36页/共70页第三十七页，共70页。v归

21、并(gubng)排序10.5 归并归并(gubng)排排序序归并排序的基本思想是：将两个(或以上)的有序表组成新的有序表。更实际的意义：可以把一个长度(chngd)为n的无序序列看成是n个长度(chngd)为1的有序子序列，首先做两两归并，得到n/2个长度(chngd)为2的子序列；再做两两归并，如此重复，直到最后得到一个长度(chngd)为n的有序序列。第37页/共70页第三十八页，共70页。v归并(gubng)排序10.5 归并归并(gubng)排排序序初始(chsh)关键字：49386597761327一趟归并后：38496597137627二趟归并后：38496597132776三趟归

22、并后：13273849657697看成是n个有序的子序列(长度为1)，然后两两归并。得到n/2个长度为2或1的有序子序列。第38页/共70页第三十九页，共70页。v归并(gubng)排序10.5 归并归并(gubng)排排序序例：关键字序列(xli)T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。第39页/共70页第四十页，共70页。212525*9362720837165449212525*49629308721637541637542125 25*4908627293082125 25*4962729308162125 25*374

23、954 627293len=1len=2len=4len=8len=16163754整个归并(gubng)排序仅需log2n趟第40页/共70页第四十一页，共70页。v一趟归并排序算法(sunf)(两路有序并为一路)10.5 归并归并(gubng)排排序序voidMerge(SR，&TR，i,m,n)/将有序的SRim和SRm+1n归并为有序的TRinfor(k=i,j=m+1;i=m&j=n;+k)if(SRi=SRj)TRk=SRi+;elseTRk=SRj+;/将SR中记录由小到大地并入(bnr)TRif(i=m)TRkn=SRim;/将剩余的SRim复制到TRif(j=n)TRkn=S

24、Rjn;/将剩余的SRjn复制到TR/Merge第41页/共70页第四十二页，共70页。v递归形式的两路归并排序(pix)算法10.5 归并归并(gubng)排排序序voidMSort(SR，&TR1，s,t)/将无序(wx)的SRst归并排序为TR1stif(s=t)TR1s=SRs;/当len=1时返回elsem=(s+t)/2;/将SRst平分为SRsm和SRm+1tMSort(SR，&TR2，s,m);/将SR一分为二,2分为4/递归地将SRsm归并为有序的TR2smMSort(SR，&TR2，m+1,t);/递归地将SRm+1t归并为有序的TR2m+1tMerge(TR2，TR1，s

25、,m,t);/将TR2sm和TR2m+1t归并到TR1st/MSort简言之，先由“长”无序变成“短”有序，再从“短”有序归并为“长”有序。初次调用时为（L,TR,1,length）第42页/共70页第四十三页，共70页。v归并排序算法(sunf)分析10.5 归并归并(gubng)排排序序时间效率O(nlog2n)一趟归并排序的操作是：调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻长度为2h的有序段，并存(bncn)放在TR1.n中，整个归并排序需要进行log2n趟，所以算法总的时间复杂度为O(nlog2n)。空间效率O(n)因为需要一个与原始

26、序列同样大小的辅助序列(TR)。这正是此算法的缺点。稳定性：稳定第43页/共70页第四十四页，共70页。v基数排序10.6 基数基数排序排序 要讨论的问题(wnt)：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样“按位值”排序？基本(jbn)思想：借助多关键字排序的思想(sxing)对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。第44页/共70页第四十五页，共70页。v基数排序10.6 基数排序基数排序 1.什么是“多关键字”排序？实现(shxin)方法？例1：对一副扑克牌该如何排序？若规定花色(hus)和面值的顺序关系为：花色(hus)：面值：2345678910JQK

27、A(1)可以先按花色(hus)排序，花色(hus)相同者再按面值排序；(2)可以先按面值排序，面值相同者再按花色(hus)排序。第45页/共70页第四十六页，共70页。v基数排序10.6 基数排序基数排序 1.什么是“多关键字”排序(pix)？实现方法？例2：职工(zhgng)分房该如何排序？规定：先以总分排序（职称分工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序。第46页/共70页第四十七页，共70页。v基数排序10.6 基数排序基数排序 多关键字排序的实现(shxin)方法通常有两种：最高位优先(yuxin)法MSD(MostSignificantDigitfi

28、rst)最低位优先(yuxin)法LSD(LeastSignificantDigitfirst)第47页/共70页第四十八页，共70页。v基数排序10.6 基数排序基数排序 例：对一副扑克牌该如何排序？答：若规定花色为第一关键字（高位），面值为第二(dr)关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。第48页/共70页第四十

29、九页，共70页。v基数排序10.6 基数排序基数排序 2.单逻辑关键字怎样(znyng)“按位值”排序？设n个记录的序列(xli)为：V0,V1,Vn-1，可以把每个记录Vi的单关键码Ki看成是一个d元组（Ki1,Ki2,Kid），则其中的每一个分量Kij(1jd)也可看成是一个关键字。注1:Ki1最高位，Kid最低位；Ki共有d位，可看成(knchn)d元组注2:每个分量Kij(1jd)有radix种取值，则称radix为基数思路：第49页/共70页第五十页，共70页。v基数排序10.6 基数排序基数排序 426(9,8,4)(0,1,9)（a,b,z）(d,i,a,n)310例1：关键码9

30、84可以看成是元组；基数radix为。例2：关键码dian可以看成是元组；基数radix为。第50页/共70页第五十一页，共70页。v基数排序10.6 基数排序基数排序 讨论讨论(toln)(toln)：是借用：是借用MSDMSD方式来排序呢，还是借用方式来排序呢，还是借用LSDLSD方式？方式？第51页/共70页第五十二页，共70页。v基数排序10.6 基数排序基数排序 例：初始(chsh)关键字序列T=（32,13,27,32*,19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。因为有分组，故此(gc)算法需递归实现。法1（MSD）：原始序列(xli)：32,13,27,32*

31、,19，33先按高位Ki1排序：（13,19）,27,（32,32*，33）再按低位Ki2排序：13,19，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33先按低位Ki2排序：32,32*,13,33,27,19再按高位Ki1排序：13,19,27,32,32*,33无需分组，易编程实现！第52页/共70页第五十三页，共70页。例：T=（02，77，70，54，64，21，55，11），用LSD排序(pix)。分析：各关键字可视为2元组；每位的取值范围是：0-9；即基数radix10。因此，特设置10个队列，并编号为0-9。1155216454707702

32、原始序列12345678先对低位扫描出队012345678910个队列计算机怎样实现计算机怎样实现(shxin)LSD(shxin)LSD算算法？法？分配(fnpi)过程收集过程下一步775564540211217012345678出队后序列775554，6421，117002又称散列过程！第53页/共70页第五十四页，共70页。0123456789再次入队再次出队再对高位扫描小结(xioji)：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。775564540211217012345678出队后序列70，776454，55211102再

33、次(zi c)分配再次(zi c)收集7770645554211102再次出队后序列这种这种LSDLSD排序方法称为：排序方法称为：基数排序第54页/共70页第五十五页，共70页。v基数排序10.6 基数排序基数排序 讨论(toln)：所用队列是顺序结构，浪费空间，能否改用链式结构？用链队列(duli)来实现基数排序链式基数排序第55页/共70页第五十六页，共70页。针对d元组中的每一位分量，把原始链表中的所有记录,按Kij的取值，让j=d,d-1,1，先“分配”到radix个链队列中去；然后(rnhu)再按各链队列的顺序，依次把记录从链队列中“收集”起来；分别用这种“分配”、“收集”的运算逐

34、趟进行排序；在最后一趟“分配”、“收集”完成后，所有记录就按其关键码的值从小到大排好序了。v链式基数排序10.6 基数排序基数排序 实现(shxin)思路：第56页/共70页第五十七页，共70页。请实现以下(yxi)关键字序列的链式基数排序：T=（614，738，921，485，637，101，215，530，790，306）例例:614921485637738101215530790306第一趟分配(fnpi)e0e1e2e3e4e5e6e7e8e9614738921485637101215530790306f0f1f2f3f4f5f6f7f8f9原始(yunsh)序列链表：r0（从最低位

35、i=3开始排序，f 是队首指针，e 为队尾指针）第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）530790921101614485215306637738r0第57页/共70页第五十八页，共70页。第一趟收集第一趟收集(shuj)(shuj)的的结果：结果：e0e1e2e3e4e5e6e7e8e9614738921485637101215530790306f0f1f2f3f4f5f6f7f8f9第二趟分配(fnpi)（按次低位 i=2）530790921101614485215306637738第二趟收集（让队尾指针(zhzhn)ei 链接到下一非空队首指针(zhzhn)f

36、i+1 ）530790921101614485215306637738r0r0第58页/共70页第五十九页，共70页。第二趟收集第二趟收集(shuj)(shuj)的结果：的结果：530790921101614485215306637738e0e1e2e3e4e5e6e7e8e9614738921485637101215530790306f0f1f2f3f4f5f6f7f8f9第三(d sn)趟分配（按最高位 i=1）第三趟收集（让队尾指针(zhzhn)ei 链接到下一非空队首指针(zhzhn)fi+1 ）530790921101614485215306637738r0r0排序结束！第59页/共

37、70页第六十页，共70页。v基数排序算法(sunf)分析10.6 基数排序基数排序 假设有n个记录(jl),每个记录(jl)的关键字有d位，每个关键字的取值有radix个,则需要radix个队列,进行d趟“分配”与“收集”。因此时间复杂度：O(d(n+radix)。基数排序需要增加n+2radix个附加链接指针，空间效率低空间复杂度：O(radix).稳定性：稳定。(一直前后有序)。用途：若基数radix相同，对于记录(jl)个数较多而关键码位数较少的情况，使用链式基数排序较好。特点：不用(byng)比较和移动，改用分配和收集，时间效率高！第60页/共70页第六十一页，共70页。v各种内部排序

38、方法(fngf)的比较10.7 内部内部(nib)排序排序方法的比较方法的比较排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入排序O(n)O(n2)O(n2)O(1)稳定希尔排序O(n1.3)O(1)不稳定直接选择排序O(n2)O(n2)O(n2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定冒泡排序O(n)O(n2)O(n2)O(1)稳定快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序（基于链式队列）O(mn)O(mn)O(mn)O(n

39、)稳定基数排序（基于顺序队列）O(mn)O(mn)O(mn)O(mn)稳定第61页/共70页第六十二页，共70页。v从上表可以得出如下几个(j)结论10.7 内部排序方法内部排序方法(fngf)的比较的比较(1)从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后(rhu)两者相比较的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。(2)简单排序包括除希尔排序之外的所有插入排序，冒泡排序和简单选择排序，其中以直接插入排序为最简单，当序列中的记录“基本有序”或n值较小时，它是最佳的排序方法，因此常将它和其它的排序方

40、法，诸如快速排序、归并排序等结合在一起使用。第62页/共70页第六十三页，共70页。v从上表(shnbio)可以得出如下几个结论10.7 内部排序内部排序(pi x)方法的比较方法的比较(4)从方法的稳定性来比较，基数排序(pix)是稳定的，所有时间复杂度为O(n2)的简单排序(pix)法（除简单选择）也是稳定的，而快排、堆排序(pix)和希尔排序(pix)等时间性能较好的排序(pix)方法都是不稳定的。一般来说，排序(pix)过程中的“比较”是在“相邻的两个记录关键字”间进行的排序(pix)方法是稳定的。(3)基数排序的时间复杂度也可写成O(dn)。因此，它最适用于n值很大而关键字较小的序列

41、。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。第63页/共70页第六十四页，共70页。v内部排序可能达到的最快速度(sd)是什么10.7 内部排序方法内部排序方法(fngf)的比较的比较本章讨论的各种排序方法，其最坏情况下的时间复杂度或为O(n2)，或为O(nlogn)，其中O(n2)是它的上界，那么O(nlogn)是否是它的下界，也就是说，能否(nnfu)找到一种排序方法，它在最坏情况下的时间复杂度低于O(nlogn)呢?第64页/共70页第六十五页，共70页。K1K2K2K3K2K3K1K3K

42、1K3否是否是K2K1K3是K2K3K1否K3K2K1否是K1K2K3否是K1K3K2K3K1=logn+log(n-1)+log(n-2)+.+log(n/2)=(n/2)log(n/2)=(n/2)logn-n/2=O(nlogn)所以只用到比较的排序算法最低时间复杂度是O(nlogn)。第67页/共70页第六十八页，共70页。本章本章(bn zhn)小结小结1.深刻理解排序的思想和各种排序方法的特点2.掌握各种排序方法的时间复杂度的分析方法3.理解排序方法“稳定”或“不稳定”的含义4.希尔排序、快速排序、堆排序、归并排序和基数排序等高效方法是本章的学习重点(zhngdin)和难点第68页/共70页第六十九页，共70页。第69页/共70页第七十页，共70页。