数据结构-第3章排序.ppt

《数据结构-第3章排序.ppt》由会员分享，可在线阅读，更多相关《数据结构-第3章排序.ppt（44页珍藏版）》请在三一办公上搜索。

1、1,上堂课要点回顾,简单排序算法：插入排序 冒泡排序 选择排序先进排序算法：快速排序,将无序子序列中的一 个或几个记录“插入”到有 序序列中，从而增加记录 的有序子序列的度。时间效率：O(n2）空间效率：O（1）算法的稳定性：稳定,每趟将相邻记录两两比较，并按“前小后大”（或“前大后小”）规则交换。每趟结束时，不仅能挤出一个最大值，若一趟中没有交换发生，还可以提前结束排序。时间效率：O(n2）空间效率：O（1）算法的稳定性：稳定,每一趟比较就找出一个最小（大）值，与待排序列最前面的位置互换即可。首先，在n个记录中选择最小者放到r1位置；然后，从剩余的n-1个记录中选择最小者放到r2位置；如此进

2、行下去，直到全部有序为止。时间效率：O(n2）空间效率：O（1）算法的稳定性：稳定,从待排序列中任取一个元素(例如取第一个)作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。时间效率：O(nlog2n）空间效率：O（log2n）算法的稳定性：不稳定,2,low,high,设 Rs=52 为枢轴。,例：,52,s,t,high,23,low,low,80,high,high,high,high,14,low,low,52,3,【教学内容】归并排序；堆排序；基数排序以及各种排

3、序算法比较【教学要求】1.熟悉快速排序、归并排序、堆排序和基数排序的思想排序过程及其依据的原则，对给定关键字的序列能够熟练写出各种排序算法的排序过程。2.掌握各种排序方法的时间复杂度。了解各种排序算法的平均情况和最坏情况的时间性能。3.掌握各种排序方法的优缺点比较及排序方法的选择。【重点与难点】快速排序、归并排序、堆排序和基数排序算法的排序过程和算法；各种排序算法的平均情况和最坏情况的时间性能及比较。,4,3.3.2 归并排序,归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。更实际的意义：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列，首先做两两归并，得到

4、n/2 个长度为 2 的子序列；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。,例：关键字序列T=（21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n 趟,void MSort(SR，/将TR2 sm和TR2 m+1t归并到TR1 st/MSort,递归形式的两路归并排序算法:参见教材P54(一路无序变为有序),简言之，先由“长”无序变成“短”有序，再从“短”有序归并为“长”有序。,初次调用时为（L,L,1,length）,一趟归并排序算

5、法:(两路有序并为一路)参见教材P53,void Merge(SR，/将剩余的SRjn复制到TR/Merge,8,0 1 2 3 4,49,13,65,97,76,7,80,SR(im),SR(m+1n),0 1 2 3 4 5 6 7,TR,0 5 6 7,7,13,49,65,76,80,97,至此 B 表的元素都已移入 C 表，只需将 A 表的剩余部分移入 C 表即可。,将两路已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止。,9,关键字序列T=52,23,80,36,68,14(s=1,t=6),52,23,80 36,

6、68,14,52,23 80,52,23,52,23,52,80,36,68 14,36,36,68,14,36,68,14,23,36,52,68,80,23,52 23,36 68,80,14,68,分解过程一路无序划分为n路有序的子序列,归并过程不断的将2路有序归并为一路有序,归并排序算法分析：,时间效率：O(nlog2n)因为在递归的归并排序算法中，函数Merge()做一趟两路归并排序，需要调用merge()函数 n/(2*len)O(n/len)次，函数Merge()调用Merge()正好log2n 次，而每次merge()要执行比较O(len)次，所以算法总的时间复杂度为O(nlo

7、g2n)。空间效率：O(n)因为需要一个与原始序列同样大小的辅助序列（TR）。这正是此算法的缺点。稳定性：稳定,3.3.3 堆排序,1.什么是堆？,堆的定义：设有n个元素的序列 k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。,或者,i=1,2,n/2,解释：如果让满足以上条件的元素序列（k1，k2，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。,2.怎样建堆？,3.怎样堆排序？,（大根堆）,例：,有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）

8、,判断它们是否“堆”？,（小根堆）,（小顶堆）（最小堆）,（大顶堆）（最大堆）,步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。,例：关键字序列T=(21，08，49，25，16，26），请建大根堆。,2.怎样建堆？,解：为便于理解，先将原始序列画成完全二叉树的形式：,完全二叉树的第一个非终端结点编号必为n/2！(性质5),注：终端结点（即叶子）没有任何子女，无需单独调整。,21,i=3:49大于26，不必调整；i=2:08小于25和16，调整；i=1:21小于25和49，要调整！,49,而且21还应当向下比较！,08,25,21,26,14,void

9、 HeapSort(HeapType/使rilength成为大根堆,建堆算法(其实是堆排序算法中的第一步）,这是针对结点 i 的堆调整函数，其含义是：从结点i开始到堆尾为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。,15,针对结点 i 的堆调整函数HeapAdjust如下：,HeapAdjust(r,i,m)current=i;child=2*i;temp=ri;while(child=rchild.key)breack;else rcurrent=rchild;current=child;child=2*child;rcurrent=temp;/Heap

10、Adjust,/temp是根，child是其左孩子,/检查是否到达当前堆尾,/让child指向两子女中的大者,/根大则不必调整，结束整个函数,/否则子女中的大者上移,/并继续向下整理！,/直到自下而上都满足堆定义，再安置老根,从结点i开始到当前堆尾m为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，即把局部调整为大根堆。,/将根下降到子女位置,关键：将堆的当前顶点输出后，如何将剩余序列重新调整为堆？方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整，如此反复直至排序结束。,3.怎样进行堆排序？,交换 1号与 6 号记录,例：对刚才建好的大顶堆进行排序：,从 1 号到 5 号 重

11、新调整为大顶堆,73,27,交换 1号与 4 号记录,从 1 号到 4 号 重新调整为大顶堆,40,55,交换 1号与 3 号记录,从 1 号到 3 号 重新调整为大顶堆,40,12,交换 1号与 2 号记录,从 1 号到 2 号 重新调整为大顶堆（已经是，无需调整）,至此堆排序结束，1.6为有序序列,堆排序算法分析：,时间效率：O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust()算法，而算法本身耗时为log2n；空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。稳定性：不稳定。优点：对小文件效果不明显，但对大文件有效。,3.4 基数排序(

12、Radix Sort),要讨论的问题：1.什么是“多关键字”排序？实现方法？2.单逻辑关键字怎样“按位值”排序？,基数排序的基本思想是：,借助多关键字排序的思想对单逻辑关键字进行排序。即：用关键字不同的位值进行排序。,1.什么是“多关键字”排序？实现方法？,例1：对一副扑克牌该如何排序？若规定花色和面值的顺序关系为：花色：面值：2 3 4 5 6 7 8 9 10 J Q K A 则可以先按花色排序，花色相同者再按面值排序；也可以先按面值排序，面值相同者再按花色排序。,例2：职工分房该如何排序？韶大规定：先以总分排序（职称分工龄分）；总分相同者，再按配偶总分排序，其次按配偶职称、工龄、人口等等

13、排序。,以上两例都是典型的多关键字排序！,多关键字排序的实现方法通常有两种：,最高位优先法MSD(Most Significant Digit first),例：对一副扑克牌该如何排序？答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。,最低位优先法LSD(Least Signifi

14、cant Digit first),26,MSD 与 LSD 的不同特点,必须将序列逐层分 割成若干子序列，然后对各子序列分 别排序。,不必分成子序列，对每个关键字都是 整个序列参加排序；通过若干次分配与 收集实现排序。,LSD,MSD,2.单逻辑关键字怎样“按位值”排序？,设n 个记录的序列为：V0,V1,Vn-1，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1,Ki2,Kid），则其中的每一个分量Kij(1 j d)也可看成是一个关键字。,4,注1：Ki1最高位，Kid最低位；Ki共有d位，可看成d元组；注2：每个分量Kij(1 j d)有radix种取值，则称radix为

15、基数。,26,(9,8,4),(0,1,9),（a,b,z）,(d,i,a,n),3,10,思路：,因为有分组，故此算法需递归实现。,讨论：是借用MSD方式来排序呢，还是借用LSD方式？,例：初始关键字序列T=（32,13,27,32*,19，33），请分别用MSD和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

16、,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。,计算机怎样实现LSD算法？,分配过程,收集过程,77,55,54，64,21，11,70,02,又称散列过程！,小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。,70，77,64,54，55,21,11,02,再次分配,再次收集,这种LSD排序方法

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

18、e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,原始序列链表：,r0,（从最低位 i=3开始排序，f 是队首指针，e 为队尾指针）,第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）,r0,第一趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第二趟分配（按次低位 i=2）,第二趟收

19、集（让队尾指针ei 链接到下一非空队首指针fi+1）,r0,r0,第二趟收集的结果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第三趟分配（按最高位 i=1）,第三趟收集（让队尾指针ei 链接到下一非空队首指针fi+1）,r0,r0,1.排序前后的n个记录都用顺序表r 存储，但建议增开n 个指针分量（转为静态链表形式）；这样在记录重排时不必移动数据，只需修改各记录的链接指针即可。2.在radix个队列中，每个队列都要设置两 个指针：int

20、 f radix指示队头(f j 初始为空）；int e radix 指向队尾（e j 不必单独初始化)；分配到同一队列的关键码要用链接指针链接起来。（注：以上一共增开了n+2*radix个附加指针分量）3.待排序记录存入r 中，r0作为头结点；每个记录都包含key分量、othernifo分量和指针域int next分量。另外，为能单独表示单关键码key的各位，将key改用向量key0d-1来表示之，这样：第p个记录的关键码的第i位可表示为：rp.keyi;第p个记录的指针分量可表示为：rp.next,如何编程实现？,先作若干说明：,void RadixSort(/选下一关键字，直到本趟分配完

21、,链表基数排序的算法：,j=0;/开始从0号队列（总共radix个队）开始收集 while(f j=0)j+;/若是空队列则跳过 r0.next=p=f j;/建立本趟收集链表的头指针 int last=ej;/建立本趟收集链表的尾指针 for(k=j+1;k radix;k+)/逐个队列链接（收集）if(f k)/若队列非空 rlast.next=f k;last=ek;/队尾指针链接 rlast.next=0;/本趟收集链表之尾部应为0/RadixSort,注：在此算法中，数组rn被反复使用，用来存放原始序列和每趟收集的结果。记录从未移动，仅指针改变。,/取第p个关键字的第i 位,/将p指

22、向下一个关键字,队不空，则新元素应链到原队尾元素之后,P是关键字序列r 的指针分量,队首为空吗？空则f(j)新入队元素,队尾新入队的元素地址,一趟“分配”过程的算法流程,假设有n 个记录,每个记录的关键字有d 位，每个关键字的取值有radix个,则需要radix个队列,进行d 趟“分配”与“收集”。分配（每趟）：T(n)=O(n)，收集（每趟）：T(n)=O(radix)，因此时间复杂度：O(d(n+radix)。基数排序需要增加n+2*radix个附加链接指针，空间效率低 空间复杂度：O（n+2*radix）.稳定性：稳定。(一直前后有序)。用途：若基数radix相同，对于记录个数较多而关键

23、码位数较少的情况，使用链式基数排序较好。,基数排序算法分析,特点：不用比较和移动，改用分配和收集，时间效率高！,一、时间性能,时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 快速排序为最好。,时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。,时间复杂度为 O(n*d)：基数排序。,1.按平均时间性能来分，有三类排序方法：,2.当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到 O(n)的时间复杂度，快速排序的时间性能蜕化为 O(n2)。,3.简单选择排序、堆排序和归并排序的时间

24、性能不随记录序列中 关键字的分布而改变。,3.5 各种排序方法的综合比较,二、空间性能,指的是排序过程中所需的辅助空间大小。,所有的简单排序方法(包括：直接插入、冒泡和简单选择)和 堆排序的空间复杂度为 O(1)；,快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助 空间；,3.归并排序所需辅助空间最多，其空间复杂度为 O(n)；,4.链式基数排序需附设队列首尾指针，则空间复杂度为 O(2*rd+n),三、排序方法的稳定性能,1.当对多关键字的记录序列进行LSD方法排序时，必须采用稳 定的排序方法。,2.对于不稳定的排序方法，只要能举出一个实例说明即可。,3.快速排序、堆排序是不稳

25、定的排序方法。,本章总结：,基于不同的“扩大”有序序列长度的方法，内部排序 方法大致可分下列几种类型：,将无序子序列中的一 个或几个记录“插入”到有 序序列中，从而增加记录 的有序子序列的长度。,通过“交换”无序序列中的记录从而 得到其中关键字最小或最大的记录，并 将它加入到有序子序列中，以此方法增 加记录的有序子序列的长度。,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它 加入到有序子序列中，以此方法增 加记录的有序子序列的长度。,通过“归并”两个 或两个以上的记录有 序子序列，逐步增加 记录有序序列的长度。,基数排序是一种基于多 关键字排序的思想，将单关 键字按基数分成“多关键字”进行排序的方法。,各种内部排序方法的比较(教材P61）,讨论：若初始记录基本无序，则选用哪些排序方法比较适合？若初始记录基本有序，则最好选用哪些排序方法？,答：对基本有序的情况，可选用堆排序、冒泡排序、归并排序等方法；在基本无序的情况下，最好选用快速排序。,