数据结构第章排序2选择排序归并排序基数排序ppt课件

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

2、关键字比较，从 n 个记录中找出关键字最小的记录，将它与第一个记录交换。 再经过 n 2 次比较，从剩余的 n 1 个记录中找出关键字次小的记录，将它与第二个记录交换。 反复上述操作，共进展 n 1 趟排序后，排序终了。 :v简单项选择择排序简单项选择择排序 10.4 选择排序选择排序例： 初始： 49 38 65 97 76 13 27 jjjjjjki =1 13 49 一趟： 13 38 65 97 76 49 27 i =2 二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13

3、 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序终了：六趟： 13 27 38 49 65 76 97 kki =6 i =3 i =4 i =5 比较次数 n - 1 n - 2 n - 6 :v简单项选择择排序算法描画简单项选择择排序算法描画10.4 选择排序选择排序void SelectSort (SqList &L) / 对顺序表对顺序表 L 作简单项选择择排作简单项选择择排序序 for (i = 1; i L.length; + i) k = i; for ( j = i+1; j = n; j+) if (L.rj.key L.r

4、k.key) k = j; if (i != k) L.riL.rk; / 与第与第 i 个记录交换个记录交换 / SelectSort :v简单项选择择排序算法分析简单项选择择排序算法分析10.4 选择排序选择排序 由于存在着不相邻元素之间的互换，因此，简单项选择择排序是“不稳定的 。 算法实现共需求进展n-1 次选择，每次选择需求进展n-i次比较(1in-1)，而每次交换最多需3次挪动，因此，总的比较次数 C = n(n-1)/2，总的挪动次数 M = 3(n-1)。故其时间复杂度为O(n2)。 空间效率：O(1)交换时用到一个暂存单元:v树形选择排序树形选择排序 (又称锦标赛排序又称锦标

5、赛排序 )10.4 选择排序选择排序根本思想：与体育竞赛时的淘汰赛类似。 首先对 n 个记录的关键字进展两两比较，得到 n/2 个优胜者(关键字小者)，作为第一步比较的结果保管下来。然后在这 n/2 个较小者之间再进展两两比较，如此反复，直到选出最小关键字的记录为止。例：关键字序列T= 21，25，49，25*，16，08，63，请给出锦标赛排序的详细实现过程。:08Winner (胜者)2108086325*2121254925*160863r1注：为便于自动处置，建议每个记录多开两个特殊分量：keyotherinfoIndex(结点位置编号）结点位置编号）Tag（是否参加比较）（是否参加比

6、较）初态补足2k( k=log2n )个叶子结点第一趟：Tree8Tree9Tree10Tree11Tree12Tree13Tree14Tree15:第二趟：082108086325*2121254925*160863161616r2Winner (胜者)求次小值16时,只需比较2次，即只比较log2n -1次。令其Tag0,不参与比较:令其Tag0,不参与比较第三趟：162116166325*2121254925*160863r3Winner (胜者)6321:082108086325*2121254925*1608636321第四趟：r4Winner (胜者)252525:08210808

7、6325*2121254925*1608631616166321252525第五趟：r5Winner (胜者)25*25*:082108086325*2121254925*160863161616632125252525*25*第六趟：r6Winner (胜者)494949:082108086325*2121254925*160863161616632125252525*25*494949第七趟：r7Winner (胜者)63:v树形选择排序算法树形选择排序算法10.4 选择排序选择排序胜者树数据结点类的定义DataNode Type data; /数据值数据值 int index; /结点在

8、满二叉树中顺序号结点在满二叉树中顺序号int active; /参选标志：参选标志：=1, 参选参选, =0, 不参选不参选:锦标赛排序的算法锦标赛排序的算法 void TournamentSort ( Type a , int n ) int bottomRowSize = PowerOfTwo ( n ); /乘幂值乘幂值 计算满足计算满足n的的2的最小次幂的数的最小次幂的数int TreeSize = 2*bottomRowSize-1; /总结点个数总结点个数int loadindex = bottomRowSize-1; /内结点个数内结点个数DataNode treeTreeSiz

9、e;int j = 0; /从从 a 向胜者树外结点复制数据向胜者树外结点复制数据for ( int i = loadindex; i TreeSize; i+) treei.index = i; if ( j n ) treei.active = 1; treei.data = aj+; else treei.active = 0; i = loadindex; /进展初始比较选择最小的项进展初始比较选择最小的项while ( i ) j = i;while ( j 2*i ) if ( !treej+1.active|treej.data treej+1.data ) /胜者送入双亲胜者送

10、入双亲tree(j-1)/2 = treej; elsetree(j-1)/2 = treej+1;j += 2;i = (i-1)/2; / i 退到双亲退到双亲, 直到直到 i=0为止为止for ( i = 0; i n-1; i+) /处置其它n-1个数据ai = tree0.data; /送出最小数据treetree0.index.active = 0; /失去参选资历 UpdateTree ( tree, tree0.index ); /调整an-1 = tree0.data; / TournamentSort :锦标赛排序中的调整算法锦标赛排序中的调整算法 void UpdateT

11、ree ( DataNode *tree, int i ) 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;else j = i+1;if ( !treei.active | !treej.active )if ( treei.active )tree(i-1)/2 = treei; /i可参选可参选, i

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

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

14、234561大根堆918566765867234561557例：有序列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

15、 选择排序选择排序212525491608123456例：关键字序列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

16、.key之中的最小者与Ri.key比较，假设Ri.key较大那么交换，这有能够破坏下一级堆。于是继续采用上述方法构造下一级堆，直到完全二叉树中结点i构成堆为止。:v怎样建堆？怎样建堆？10.4 选择排序选择排序:v怎样建堆？怎样建堆？10.4 选择排序选择排序 void HeapAdjust(SqList H， int s， int m) /知知H.rs.m中记录的关键字除中记录的关键字除H.rs.key之外均满足堆的定义，之外均满足堆的定义，/本函数调整本函数调整H.rs的关键字，使的关键字，使H.rs.m成为一个大顶堆成为一个大顶堆 rc = H.rs; for (j=2*s; j=m;

17、j*=2) /沿沿key较大的孩子结点向下挑选较大的孩子结点向下挑选, j为为key较大的记录的下标较大的记录的下标 if(j0;-i) /把把H.r1.length建成大顶堆建成大顶堆 HeapAdjust(H,i,H.length); for(i=H.length; i1; -i) /将堆顶记录和当前未经排将堆顶记录和当前未经排 /序子序列序子序列H.r.1.i中最后一个记录相互交换中最后一个记录相互交换 H.r1 H.ri； HeapAdjust(H,1,i-1); /将将H.R1.i-1重新调整为大顶堆重新调整为大顶堆 /HeapSort :v附附1：基于初始堆进展堆排序的算法步骤：基

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

19、值 ，使H.rsm为堆附2：算法流程比较左右孩子大小，j指向大者比较大孩子与rc的大小假设大向上浮:v堆排序的效率分析堆排序的效率分析10.4 选择排序选择排序 在整个堆排序中，共需求进展 n+n/2 -1 次挑选运算，每次挑选运算进展双亲和孩子或兄弟结点的排序码的比较和挪动次数都不会超越完全二叉树的深度。故每次挑选运算的时间复杂度为O(log2n)，那么整个堆排序过程的时间复杂度为O(nlog2n) 。 堆排序在最坏情况下，时间复杂度也为O(nlog2n)。相对于快速排序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换运用。 由于存在着不相邻元素之间的互换，因此，堆排序

20、是一种不稳定的排序方法。:v堆排序的效率分析堆排序的效率分析10.4 选择排序选择排序 时间效率： O(nlog2n)。由于整个排序过程中需求调用n-1次HeapAdjust( )算法， HeapAdjust( )而算法本身耗时为log2n； 空间效率：O(1)。仅在第二个for循环中交换记录时用到一个暂时变量temp。 稳定性： 不稳定。 优点：对少量数据效果不明显，但对大量数据有效。:v归并排序归并排序10.5 归并排序归并排序归并排序的根本思想是：将两个(或以上)的有序表组成新的有序表。更实践的意义：可以把一个长度为n的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得

21、到 n / 2 个长度为 2 的子序列 ；再做两两归并，如此反复，直到最后得到一个长度为n 的有序序列。:v归并排序归并排序10.5 归并排序归并排序初始关键字： 49 38 65 97 76 13 27 一趟归并后： 38 49 65 97 13 76 27 二趟归并后： 38 49 65 97 13 27 76 三趟归并后： 13 27 38 49 65 76 97 看成是 n 个有序的子序列(长度为 1)，然后两两归并。 得到 n/2 个长度为2 或 1 的有序子序列。 :v归并排序归并排序10.5 归并排序归并排序例：关键字序列T= 21，25，49，25*，93，62，72，08，3

22、7，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+1n归并为有序的TRin fo

23、r(k=i , j=m+1; i=m & j=n; +k ) if ( SRi= SRj )TRk=SRi+; else TRk=SRj+; / 将SR中记录由小到大地并入TR if (i=m) TRkn=SRim; / 将剩余的SRim复制到TR if (j=n) TRkn=SRjn; / 将剩余的SRjn复制到TR / Merge:v递归方式的两路归并排序算法递归方式的两路归并排序算法10.5 归并排序归并排序 void MSort (SR，&TR1，s, t) / 将无序的SRst归并排序为TR1st if ( s=t )TR1s=SRs; / 当len=1时前往 els

24、e m=(s+t)/2; / 将SR st平分为SR sm和SR m+1t MSort (SR，&TR2，s, m); / 将SR 一分为二, 2分为4 / 递归地将SR sm归并为有序的TR2sm MSort (SR，&TR2，m+1, t ); / 递归地将SR m+1t归并为有序的TR2m+1t Merge(TR2， TR1， s, m, t ); / 将TR2 sm和TR2 m+1t归并到TR1 st / MSort简言之，先由“长无序变成“短有序， 再从“短有序归并为“长有序。初次调用时为L, TR, 1, length:v归并排序算法分析归并排序算法分析10.5 归

25、并排序归并排序 时间效率 O(nlog2n) 一趟归并排序的操作是：调用n/2h次算法merge将SR1.n中前后相邻且长度为h的有序段进展两两归并，得到前后相邻长度为2h的有序段，并存放在TR1.n中，整个归并排序需求进展log2n趟，所以算法总的时间复杂度为O(nlog2n)。 空间效率 O(n) 由于需求一个与原始序列同样大小的辅助序列(TR)。这正是此算法的缺陷。 稳定性：稳定:v基数排序基数排序 10.6 基数排序基数排序 要讨论的问题：1. 什么是“多关键字排序？实现方法？2. 单逻辑关键字怎样“按位值排序？根本思想：借助多关键字排序的思想对单逻辑关键字进展排序。即：用关键字不同的

26、位值进展排序。:v基数排序基数排序 10.6 基数排序基数排序 1. 什么是“多关键字排序？实现方法？例1：对一副扑克牌该如何排序？假设规定花样和面值的顺序关系为：花样： 面值：2 3 4 5 6 7 8 9 10 J Q K A(1)可以先按花样排序，花样一样者再按面值排序；(2)可以先按面值排序，面值一样者再按花样排序。:v基数排序基数排序 10.6 基数排序基数排序 1. 什么是“多关键字排序？实现方法？例2：职工分房该如何排序？规定：先以总分排序职称分工龄分；总分一样者，再按配偶总分排序，其次按配偶职称、工龄、人口等等排序。:v基数排序基数排序 10.6 基数排序基数排序 多关键字排序

27、的实现方法通常有两种： 最高位优先法MSD (Most Significant Digit first) 最低位优先法LSD (Least Significant Digit first):v基数排序基数排序 10.6 基数排序基数排序 例：对一副扑克牌该如何排序？答：假设规定花样为第一关键字高位，面值为第二关键字低位，那么运用MSD和LSD方法都可以到达排序目的。MSD方法的思绪：先设立4个花样“箱，将全部牌按花样分别归入4个箱内每个箱中有13张牌；然后对每个箱中的牌按面值进展插入排序或其它稳定算法。LSD方法的思绪：先按面值分成13堆每堆4张牌，然后对每堆中的牌按花样进展排序用插入排序等稳

28、定的算法。:v基数排序基数排序 10.6 基数排序基数排序 2. 单逻辑关键字怎样“按位值排序？设n个记录的序列为：V0, V1, , Vn-1 ，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组Ki1, Ki2, , Kid，那么其中的每一个分量Kij ( 1 j d ) 也可看成是一个关键字。注1: Ki1最高位，Kid最低位；Ki共有d位，可看成d元组注2: 每个分量Kij (1 j d ) 有radix种取值，那么称radix为基数思绪：:v基数排序基数排序 10.6 基数排序基数排序 426(9, 8, 4)(0, 1, , 9)a, b, , z(d, i, a, n)310

29、例1：关键码984可以看成是 元组；基数radix 为 。例2：关键码dian可以看成是 元组；基数radix 为 。:v基数排序基数排序 10.6 基数排序基数排序 :v基数排序基数排序 10.6 基数排序基数排序 例：初始关键字序列T=32, 13, 27, 32*, 19，33，请分别用MSD和LSD进展排序，并讨论其优缺陷。由于有分组，故此算法需递归实现。法1MSD：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：13, 19, 27, 32, 32*，33 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33法2LSD： 原始序列

30、： 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；即基数radix 10 。因此，特设置10个队列，并编号为0-9。1155216454707702原始序列12345678先对低位扫描出队012345678910个队列计算机怎样实现LSD算法？分配过程搜集过程下一步7755645402112170123456

31、78出队后序列775554，6421，117002又称散列过程！:0123456789再次入队再次出队再对高位扫描小结：排序时经过了反复的“分配和“搜集过程。当对关键字一切的位进展扫描排序后，整个序列便从无序变为有序了。775564540211217012345678出队后序列70，776454，55211102再次分配再次搜集7770645554211102再次出队后序列这种LSD排序方法称为： 基数排序:v基数排序基数排序 10.6 基数排序基数排序 讨论：所用队列是顺序构造，浪费空间，能否改用链式构造？用链队列来实现基数排序链式基数排序: 针对针对 d 元组中的每一位分量，把原始链表中元

32、组中的每一位分量，把原始链表中的一切记录的一切记录, 按按Kij的取值，让的取值，让 j = d, d-1, , 1， 先先“分配分配到到radix个链队列中去；个链队列中去； 然后再按各链队列的顺序，依次把记录从链队列中然后再按各链队列的顺序，依次把记录从链队列中“搜集搜集起来；起来； 分别用这种分别用这种“分配分配、“搜集搜集的运算逐趟进展排序；的运算逐趟进展排序； 在最后一趟在最后一趟“分配分配、“搜集搜集 完成后，一切记录就按完成后，一切记录就按其关键码的值从小到大排好序了。其关键码的值从小到大排好序了。v链式基数排序链式基数排序10.6 基数排序基数排序 实现思绪：: 请实现以下关键

33、字序列的链式基数排序：T=614，738，921，485，637， 101，215，530，790，306例:614921485637738101215530790306第一趟分配e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9原始序列链表：r0从最低位 i = 3开场排序，f 是队首指针，e 为队尾指针第一趟搜集让队尾指针ei 链接到下一非空队首指针fi+1 即可530790921101614485215306637738r0:第一趟搜集的结果：e0 e1 e2 e

34、3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第二趟分配按次低位 i = 2 530790921101614485215306637738第二趟搜集让队尾指针ei 链接到下一非空队首指针fi+1 530790921101614485215306637738r0r0:第二趟搜集的结果：530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4

35、 f5 f6 f7 f8 f9第三趟分配按最高位 i = 1 第三趟搜集让队尾指针ei 链接到下一非空队首指针fi+1 530790921101614485215306637738r0r0排序终了！:v基数排序算法分析基数排序算法分析10.6 基数排序基数排序 假设有n 个记录, 每个记录的关键字有d 位，每个关键字的取值有radix个, 那么需求radix个队列, 进展d趟“分配与“搜集。因此时间复杂度：O( d ( n+radix ) )。基数排序需求添加n+2radix个附加链接指针，空间效率低 空间复杂度：O(radix).稳定性：稳定。(不断前后有序)。用途：假设基数radix一样，对于记录个数较多而关键码位数较少的情况，运用链式基数排序较好。特点：不用比较和挪动，改用分配和搜集，时间效率高！:v各种内部排序方法的比较各种内部排序方法的比较10.7 内部排序方法的比较内部排序方法的比较排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入排序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