数据结构第10章排序2选择排序归并排序基数排序.pptx

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

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2011年3月12日第第1010章章 内部排序内部排序选择排序(直接排序、堆排序)概述插入排序(直接排序、折半排序、希尔排序)交换排序(冒泡排序、快速排序)归并排序基数排序v选择选择排序排序10.4选择排序选择排序基本思想：第i趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。1.简单选择排序2.树形选择排序3.堆排序v简单简单选择排序选择排序10.4选择排序选择排序排序过程：u首先通过n 1次关键字比较，从n个记录中找出关键字最

2、小的记录，将它与第一个记录交换。u再通过n 2次比较，从剩余的n1个记录中找出关键字次小的记录，将它与第二个记录交换。u重复上述操作，共进行n1趟排序后，排序结束。v简单简单选择排序选择排序10.4选择排序选择排序例：初始：49386597761327jjjjjjki=11349一趟：13386597764927i=2二趟：13276597764938三趟：13273897764965四趟：13273849769765五趟：13273849659776六趟：13273849657697排序结束：六趟：13273849657697kki=6i=3i=4i=5比较次数n-1n-2n-6v简单简单选

3、择排序算法描述选择排序算法描述10.4选择排序选择排序voidSelectSort(SqList&L)/对顺序表L作简单选择排序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个记录交换/SelectSortv简单简单选择排序算法分析选择排序算法分析10.4选择排序选择排序由于存在着不相邻元素之间的互换，因此，简单选择排序是“不稳定的”。算法实现共需要进行n-1次选择，每次选择需要进行n-i次比较(1in-1)，而每次交换最多需3次移动，因此，总的比较次数C=n(n-1

4、)/2，总的移动次数M=3(n-1)。故其时间复杂度为O(n2)。空间效率：O(1)交换时用到一个暂存单元v树形选择树形选择排序排序(又称又称锦标赛排序锦标赛排序)10.4选择排序选择排序基本思想：与体育比赛时的淘汰赛类似。首先对n 个记录的关键字进行两两比较，得到n/2个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这n/2个较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。例：关键字序列T=（21，25，49，25*，16，08，63），请给出锦标赛排序的具体实现过程。08Winner(胜者)2108086325*2121254925*160863r1注：为便于

5、自动处理，建议每个记录多开两个特殊分量：keyotherinfoIndex(结点位置编号）结点位置编号）Tag（是否参加比较）（是否参加比较）初态补足2k(k=log2n)个叶子结点第一趟：Tree8Tree9Tree10Tree11Tree12Tree13Tree14Tree15第二趟：082108086325*2121254925*160863161616r2Winner(胜者)求次小值16时,只需比较2次，即只比较log2n-1次。令其Tag0,不参与比较令其Tag0,不参与比较第三趟：162116166325*2121254925*160863r3Winner(胜者)632108210

6、8086325*2121254925*1608636321第四趟：r4Winner(胜者)252525082108086325*2121254925*1608631616166321252525第五趟：r5Winner(胜者)25*25*082108086325*2121254925*160863161616632125252525*25*第六趟：r6Winner(胜者)494949082108086325*2121254925*160863161616632125252525*25*494949第七趟：r7Winner(胜者)63v树形选择排序树形选择排序算法算法10.4选择排序选择排序胜者

7、树数据结点类的定义DataNodeTypedata;/数据值intindex;/结点在满二叉树中顺序号intactive;/参选标志：=1,参选,=0,不参选锦标赛排序的锦标赛排序的算法算法voidTournamentSort(Typea,intn)intbottomRowSize=PowerOfTwo(n);/乘幂值计算满足n的2的最小次幂的数intTreeSize=2*bottomRowSize-1;/总结点个数intloadindex=bottomRowSize-1;/内结点个数DataNodetreeTreeSize;intj=0;/从a向胜者树外结点复制数据for(inti=load

8、index;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|treej.datatreej+1.data)/胜者送入双亲tree(j-1)/2=treej;elsetree(j-1)/2=treej+1;j+=2;i=(i-1)/2;/i退到双亲,直到i=0为止for(i=0;in-1;i+)/处理其它n-1个数据ai=tree0.data;/送出

9、最小数据treetree0.index.active=0;/失去参选资格UpdateTree(tree,tree0.index);/调整an-1=tree0.data;/TournamentSort锦标赛排序中的调整算法锦标赛排序中的调整算法voidUpdateTree(DataNode*tree,inti)if(i%2=0)tree(i-1)/2=treei-1;/i偶数,对手左结点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|!

10、treej.active)if(treei.active)tree(i-1)/2=treei;/i可参选,i上elsetree(i-1)/2=treej;/否则,j上else/两方都可参选if(treei.datatreej.data)tree(i-1)/2=treei;/关键码小者上elsetree(i-1)/2=treej;i=(i-1)/2;/i上升到双亲v树形选择排序算法分析树形选择排序算法分析10.4选择排序选择排序锦标赛排序构成的树是满(完全)二叉树，其深度为log2n +1，其中n为待排序元素个数。时间复杂度：O(nlog2n)n个记录各自比较约log2n次空间效率：O(n)胜者

11、树的附加内结点共有n-1个！稳定性：稳定左右结点相同者左为先n=2k=叶子总数v堆排序堆排序10.4选择排序选择排序1.什么是堆？堆的定义：设有n个元素的序列k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。kik2ikik2i+1ki k2ikik2i+1或者i=1,2,n/22.怎样建堆？3.怎样堆排序？解释：如果让满足以上条件的元素序列(k1，k2，kn)顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于(或小于)其左右孩子，此树的根结点(即堆顶)必最大(或最小)。v堆排序堆排序10.4选择排序选择排序082546495867234561（大根堆）91856676586

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

13、例：关键字序列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)注：终端结点（即叶子）没有任何子女，无需单独调整。v怎样怎样建堆？建堆？10.4选择排序选择排序这个自堆顶至叶子的调整过程称为“筛选”。筛选:假若完全二叉树的某一个结点i，它的左、右子树已是堆。需要将R2i.key与R2i+1.key之中的最小者与Ri.key比较，若Ri.key较大则交换

14、，这有可能破坏下一级堆。于是继续采用上述方法构造下一级堆，直到完全二叉树中结点i构成堆为止。v怎样怎样建堆？建堆？10.4选择排序选择排序v怎样怎样建堆？建堆？10.4选择排序选择排序voidHeapAdjust(SqListH，ints，intm)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数调整H.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);fo

15、r(i=H.length;i1;-i)/将堆顶记录和当前未经排/序子序列H.r.1.i中最后一个记录相互交换H.r1H.ri；HeapAdjust(H,1,i-1);/将H.R1.i-1重新调整为大顶堆/HeapSortv附附1：基于初始堆进行堆排序的算法：基于初始堆进行堆排序的算法步骤步骤10.4选择排序选择排序1.堆的第一个对象V0具有最大的关键码，将V0与Vn对调，把具有最大关键码的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即V0位置。2.再对调V0和Vn-1，调用对前n-2个对象重新调整，如此反复，最后得到全部排序好的

16、对象序列。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.rsm为堆附2：算法流程比较左右孩子大小，j指向大者比较大孩子与rc的大小若大向上浮v堆堆排序的效率分析排序的效率分析10.4选择排序选择排序在整个堆排序中，共需要进行n+n/2-1次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度。故每次筛选运算的时间复杂度为O(log2n)，则整个堆排序过程的时间复杂度为O(n

17、log2n)。堆排序在最坏情况下，时间复杂度也为O(nlog2n)。相对于快速排序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换使用。由于存在着不相邻元素之间的互换，因此，堆排序是一种不稳定的排序方法。v堆堆排序的效率分析排序的效率分析10.4选择排序选择排序时间效率：O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust()算法，HeapAdjust()而算法本身耗时为log2n；空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。稳定性：不稳定。优点：对少量数据效果不明显，但对大量数据有效。v归并排序归并排序10.5归并

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

19、序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。212525*9362720837165449212525*49629308721637541637542125 25*4908627293082125 25*4962729308162125 25*374954 627293len=1len=2len=4len=8len=16163754整个归并排序仅需log2n趟v一一趟归并排序趟归并排序算法算法(两路有序并为一路两路有序并为一路)10.5归并排序归并排序void Merge(SR，&TR，i,m,n)/将有序的SRim和SRm+1

20、n归并为有序的TRinfor(k=i,j=m+1;i=m&j=n;+k)if(SRi=SRj)TRk=SRi+;elseTRk=SRj+;/将SR中记录由小到大地并入TRif(i=m)TRkn=SRim;/将剩余的SRim复制到TRif(j=n)TRkn=SRjn;/将剩余的SRjn复制到TR/Mergev递归递归形式的两路归并排序算法形式的两路归并排序算法10.5归并排序归并排序void MSort(SR，&TR1，s,t)/将无序的SRst归并排序为TR1stif(s=t)TR1s=SRs;/当len=1时返回elsem=(s+t)/2;/将SRst平分为SRsm和SRm+1t MSort

21、(SR，&TR2，s,m);/将SR一分为二,2分为4/递归地将SRsm归并为有序的TR2sm MSort(SR，&TR2，m+1,t);/递归地将SRm+1t归并为有序的TR2m+1tMerge(TR2，TR1，s,m,t);/将TR2sm和TR2m+1t归并到TR1st/MSort简言之，先由“长”无序变成“短”有序，再从“短”有序归并为“长”有序。初次调用时为（L,TR,1,length）v归并排序算法分析归并排序算法分析10.5归并排序归并排序时间效率O(nlog2n)一趟归并排序的操作是：调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻长

22、度为2h的有序段，并存放在TR1.n中，整个归并排序需要进行log2n趟，所以算法总的时间复杂度为O(nlog2n)。空间效率O(n)因为需要一个与原始序列同样大小的辅助序列(TR)。这正是此算法的缺点。稳定性：稳定v基数基数排序排序10.6基数基数排序排序要讨论的问题：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样“按位值”排序？基本思想：借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。v基数基数排序排序10.6基数排序基数排序1.什么是“多关键字”排序？实现方法？例1：对一副扑克牌该如何排序？若规定花色和面值的顺序关系为：花色：面值：2345678

23、910JQKA(1)可以先按花色排序，花色相同者再按面值排序；(2)可以先按面值排序，面值相同者再按花色排序。v基数基数排序排序10.6基数排序基数排序1.什么是“多关键字”排序？实现方法？例2：职工分房该如何排序？规定：先以总分排序（职称分工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序。v基数基数排序排序10.6基数排序基数排序多关键字排序的实现方法通常有两种：最高位优先法MSD(MostSignificantDigitfirst)最低位优先法LSD(LeastSignificantDigitfirst)v基数基数排序排序10.6基数排序基数排序例：对一副扑克牌该

24、如何排序？答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。v基数基数排序排序10.6基数排序基数排序2.单逻辑关键字怎样“按位值”排序？设n个记录的序列为：V0,V1,Vn-1，可以把每个记录Vi的单关键码Ki看成是一个d元组（Ki1,Ki2,Kid），则其中的每一个分量Kij(1

25、jd)也可看成是一个关键字。注1:Ki1最高位，Kid最低位；Ki共有d位，可看成d元组注2:每个分量Kij(1jd)有radix种取值，则称radix为基数思路：v基数基数排序排序10.6基数排序基数排序426(9,8,4)(0,1,9)（a,b,z）(d,i,a,n)310例1：关键码984可以看成是元组；基数radix为。例2：关键码dian可以看成是元组；基数radix为。v基数基数排序排序10.6基数排序基数排序讨论：讨论：是借用MSD方式来排序呢，还是借用LSD方式？v基数基数排序排序10.6基数排序基数排序例：初始关键字序列T=（32,13,27,32*,19，33），请分别用M

26、SD和LSD进行排序，并讨论其优缺点。因为有分组，故此算法需递归实现。法1（MSD）：原始序列：32,13,27,32*,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无需分组，易编程实现！例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：各关键字可视为2元组；每位的取值范围是：0-9；即基数radix10。因

27、此，特设置10个队列，并编号为0-9。1155216454707702原始序列12345678先对低位扫描出队012345678910个队列计算机怎样实现LSD算法？分配过程收集过程下一步775564540211217012345678出队后序列775554，6421，117002又称散列过程！0123456789再次入队再次出队再对高位扫描小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。775564540211217012345678出队后序列70，776454，55211102再次分配再次收集7770645554211102再次

28、出队后序列这种LSD排序方法称为：基数排序v基数基数排序排序10.6基数排序基数排序讨论：所用队列是顺序结构，浪费空间，能否改用链式结构？用链队列来实现基数排序链式基数排序针对d 元组中的每一位分量，把原始链表中的所有记录,按Kij的取值，让j=d,d-1,1，先“分配”到radix个链队列中去；然后再按各链队列的顺序，依次把记录从链队列中“收集”起来；分别用这种“分配”、“收集”的运算逐趟进行排序；在最后一趟“分配”、“收集”完成后，所有记录就按其关键码的值从小到大排好序了。v链式链式基数排序基数排序10.6基数排序基数排序实现思路：请实现以下关键字序列的链式基数排序：T=（614，738，

29、921，485，637，101，215，530，790，306）例:614921485637738101215530790306第一趟分配e0e1e2e3e4e5e6e7e8e9614738921485637101215530790306f0f1f2f3f4f5f6f7f8f9原始序列链表：r0（从最低位 i=3开始排序，f 是队首指针，e 为队尾指针）第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）530790921101614485215306637738r0第一趟收集的结果：e0e1e2e3e4e5e6e7e8e96147389214856371012155307903

30、06f0f1f2f3f4f5f6f7f8f9第二趟分配（按次低位 i=2）530790921101614485215306637738第二趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）530790921101614485215306637738r0r0第二趟收集的结果：530790921101614485215306637738e0e1e2e3e4e5e6e7e8e9614738921485637101215530790306f0f1f2f3f4f5f6f7f8f9第三趟分配（按最高位 i=1）第三趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）5307909211016

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

32、部排序方法的方法的比较比较排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入排序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)稳定基数排序（基于顺序队列）O(mn)O(mn)O

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

34、论10.7内部排序方法的比较内部排序方法的比较(4)从方法的稳定性来比较，基数排序是稳定的，所有时间复杂度为O(n2)的简单排序法（除简单选择）也是稳定的，而快排、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。一般来说，排序过程中的“比较”是在“相邻的两个记录关键字”间进行的排序方法是稳定的。(3)基数排序的时间复杂度也可写成O(dn)。因此，它最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。v内部排序内部排序可能达到的最快速度是什么可能达到的最快速度是什么

35、10.7内部排序方法的比较内部排序方法的比较本章讨论的各种排序方法，其最坏情况下的时间复杂度或为O(n2)，或为O(nlogn)，其中O(n2)是它的上界，那么O(nlogn)是否是它的下界，也就是说，能否找到一种排序方法，它在最坏情况下的时间复杂度低于O(nlogn)呢?K1K2K2K3K2K3K1K3K1K3否是否是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)。本章小结本章小结1.深刻理解排序的思想和各种排序方法的特点2.掌握各种排序方法的时间复杂度的分析方法3.理解排序方法“稳定”或“不稳定”的含义4.希尔排序、快速排序、堆排序、归并排序和基数排序等高效方法是本章的学习重点和难点武汉科技大学Wuhan University of Science and Technology