数据结构课件-第10章-内部排序答案.ppt

《数据结构课件-第10章-内部排序答案.ppt》由会员分享，可在线阅读，更多相关《数据结构课件-第10章-内部排序答案.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、10.1 排序的定义和方法 什么是“排序”？简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。例如，将下列记录序列 52,49,80,36,14,58,61,23,97,75 调整为序列 14,23,36,49,52,58,61,75,80,97 第十章第十章 内部排序内部排序一般情况下，对排序的定义为：假设含有n个记录的序列为：r1,r2,rn(10-1)它们的关键字相应为k1,k2,kn对式（10-1）的记录序列进行排序就是要确定序号1,2,n的一种排列 P1,P2,Pn使其相应的关键字满足如下的非递减（或非递增）的关系：(10-2)就是使式(10-1)的记录序列重新排列成一个按

2、关键字有序的序列 rp1,rp2,rpn (10-3)当待排序记录中的关键字(i=1,2,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是唯一；若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。假设ki=kj(1in,1jn,ij)，且在排序前的序列中，ri领先于rj(即ij)。若在排序后的序列中ri仍领先于rj，则称所用的排序方法是稳定的稳定的；反之，若可能使排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的不稳定的 根据涉及的存储器不同，将排序方法分为两大类：1）内部排序内部排序：在排序进行的过程中不使用计算机外部 存储器的排序过程。2）外部

3、排序外部排序：在排序进行的过程中需要对外存进行访 问的排序过程。内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程有序序列有序序列有序序列有序序列无序序列无序序列无序序列无序序列有序序列有序序列有序序列有序序列无序序列无序序列无序序列无序序列一趟排序 逐步扩大记录的有序序列长度排序的方法大致有一下几类：插入类、交换类、选择类、归并类、其他类将无序子序列中的一个或几个记录插入到有序序列中从而增加记录的有序子序列的长度通过交换无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它加入有序子序列中，以此方法增加有序子序列的长度。从记录的无序子序列中选择关键字最小或最大的记录，

4、并将它加入有序子序列中，以此方法增加有序子序列的长度。通过归并两个或两个以上记录的有序子序列，逐步增加有序子序列的长度。按排序过程中所需的工作量来分：1)简单的排序方法 时间复杂度O（n2）2)先进的排序方法 时间复杂度O（nlogn）3)基数排序 时间复杂度O（dn）10.2 插入排序 插入排序的准则:在有序序列中插入新的记录以达到扩大有序区的长度的目的。有序序列有序序列有序序列有序序列R1.i-1R1.i-1无序序列无序序列无序序列无序序列Ri.nRi.n 有序序列有序序列有序序列有序序列R1.iR1.i无序序列无序序列无序序列无序序列一趟插入排序的基本思想：RiRi 有序序列有序序列有序

5、序列有序序列R1.i-1R1.i-1无序序列无序序列无序序列无序序列Ri.nRi.n 由此实现一趟插入排序的步骤为：1)在 R1.i-1 中查找 Ri 的插入位置，即确定j(0ji)使得 R1.j.keyRi.keyRj+1.i-1.key2)将 Rj+1.i-1 中的记录后移一个位置；3)将 Ri 插入到 j+1 的位置。为了避免在查找过程中判别循环变量是否出界，设置R0为监视哨，并在查找的同时进行记录后移，如动画flash10-2-2所示。算法算法 10.1void InsertPass(SqList&L,int i)/已知已知L.r1.i-1中的记录已按关键字非递减的顺序有序排列中的记录

6、已按关键字非递减的顺序有序排列,/本算法实本算法实 现将现将L.ri插入其中插入其中,并保持并保持L.r1.i中记录按关键字中记录按关键字非非 /递减顺序有序递减顺序有序L.r0=L.ri;/复制为哨兵for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置/InsertPass具体做法不同可分为以下几种插入排序方法：具体做法不同可分为以下几种插入排序方法：直接插入排序直接插入排序折半插入排序折半插入排序表插入排序表插入排序希尔排序希尔排序缩小增量插入排序10.2.1 直接插入排序直接插入排序直接插入排序利用直接插

7、入排序利用顺序查找顺序查找实现在实现在R1.i-1中查找中查找Ri的插入位置的插入位置 算法算法 10.2void InsertSort(SqList&L,int i)/对顺序表对顺序表L进行直接插入排序进行直接插入排序 for（i=2;i=L.length;+i）if(L.ri.key L.ri-1.key)L.r0=L.ri;/复制为哨兵 for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移 L.rj+1=L.r0;/插入到正确位置 /InsertSort最好的情况（关键字记录在序列中顺序有序）直接插入排序时间效率分析直接插入排序时间效率分析实现

8、排序的基本操作有两个：实现排序的基本操作有两个：1）比较比较序列中两个关键字的大小序列中两个关键字的大小2）移动移动记录记录最坏的情况（关键字记录在序列中逆序有序）比较比较的次数的次数移动移动的次数的次数比较比较的次数的次数移动移动的次数的次数待排记录待排记录序列状态序列状态比较比较次数次数移动移动次数次数正序n-10逆序(n+2)(n-1(n+2)(n-1）/2/2(n+4)(n-1(n+4)(n-1）/2/2一般情况下，直接插入排序的时间复杂度为O(n2)。10.2.2 折半插入排序 由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用“折半查找”查询插入位置，由此得到的插

9、入排序算法为“折半插入排序”。如动画flash10-2-3所示演示过程Void BInsertSort(SqList&L)/对顺序表L进行折半插入排序for(i=2;i=L.length;+i)L.r0=L.ri;/将L.ri暂存到 L.r0 low=1;high=i-1;/折半查找插入的位置 while(low=high)m=(low+high)/2;if(L.r0.key=high+1;-j)L.rj+1=L.rj;/记录后移 L.rhigh+1=L.r0;/插入/for/BInserSort在L.r1.i-1折半查找插入位置10.2.3 表插入排序表插入排序 为了减少在排序过程中进行移动

10、记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们应该在的位置上 这个静态链表由存储记录的顺序表和附加的指针数组构成，静态链表中的指针实际上指的是数组的下标。表插入排序分两步进行：首先构造一个有序链表（循环链表）；然后按照“附加指针”的指示将结点中的记录重新排列成一个有序序列。如动画flsh10-2-4 表插入排序的过程举例k kj ji i0 01 12 23 34 45 56 67 7R1.i-1 已经形成循环链表，Ri为要插入的记录，插入位置为Rj 与Rk之间，k指示为j的指针域所指示单元Ri

11、.next=k;Rj.next=i;k kj ji iRi.next=k;Rj.next=i;关键字关键字关键字关键字2929636318183737545412124545指针指针指针指针3 34 40 01 15 52 20 01 12 23 34 45 56 67 7关键字关键字关键字关键字2929636318183737545412124545指针指针指针指针3 34 40 01 12 20 01 12 23 34 45 56 67 7k kj ji i关键字关键字关键字关键字2929636318183737545412124545指针指针指针指针3 34 40 01 15 52 2完

12、成表插入之后，调整重新排列关键字关键字关键字关键字2929636318183737545412124545指针指针指针指针6 64 40 01 17 72 23 35 50 01 12 23 34 45 56 67 7i ip pq q29294 412123 312126 6pi为止。10.2.4 希尔排序 希尔排序又称“缩小增量排序”，它的基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。例如一个含11个关键字的序列(16,25,12,30,47,11,23,36,9,18,31),先对它进行“增量为5”的插入排序(r1,r6,r11)(r2,r7)

13、(r5,r10)然后将增量“缩小到3”，(r1,r4,r7,r10)(r2,r5,r8,r11)(r3,r6,r9)之后经过最后一趟插入排序即得到有序序列希尔排序举例 之后经过最后一趟插入排序即得到有序序列(16,25,12,30,47,11,23,36,9,18,31)(11,23,12,9,18,16,25,36,30,47,31)先对它进行“增量为5”的插入排序然后将增量“缩小到3”(9,18,12,11,23,16,25,31,30,47,36)(9,11,12,16,18,23,25,30,31,36,47)过程如动画flash10-2-5算法参见教材P272 算法10.4-10.5

14、10.3 交换排序法 起泡排序是交换类排序方法中的一种简单排序方法。基本思想为：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。如动画flash10-3-1 10.3.1 起泡排序 起泡排序的过程：首先第一个记录的关键字和第二个记录的关键字比较，若逆序，则两个记录交换，然后比较第二个记录和第三个记录的关键字。以此类推，直到第n-1个记录和第n个记录的关键字进行比较为止。上述这个过程称为第一趟气泡排序。结果是关键字最大的记录落在最后一个位置上。整个排序过程需要进行K趟起泡排序。结束的条件是：在一趟排序过程中没有进行交换记录的操作。例如：如动画flash10-3-210.3.2

15、快速排序快速排序 快速排序则是通过一趟排序选定一个关键字介于中间的记录，从而使剩余记录可以分成两个子序列分别继续排序，通常称该记录为枢轴。一趟快速排序的具体做法：附设两个指针low和high，初始值分别为low和high，枢轴记录的关键字为piovtkey，首次从high所指位置向前搜索到第一个关键字小于piovtkey的记录和枢轴记录互相交换，然后从low向后搜索第一个关键字大于piovtkey的记录和枢轴记录互相交换。重复这两步，直至low=high为止。算法参见教材P274 算法10.6例如，关键字序列(52,49,80,36,14,75,58,97,23,61)经第1趟快速排序之后为(

16、23,49,14,36)52(75,58,97,80,61)经第2趟快速排序之后为(14)23(49,36)52(61,58)75(80,97)经第3趟快速排序之后为(14,23,36,49,52,58,61,75,80,97)一趟快排也称“一次划分”，即将待排序列 Rs.t“划分”为两个子序列Rs.i-1 和 Ri+1.t，i 为一次划分之后的枢轴位置。如动画flsah10-3-410.4 选择排序法 10.4.1 简单选择排序 选择排序的基本思想：在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。第 i趟简单选择排序的作法：在后 n-i+1 个记录中选出关键字最小的记

17、录，并将它和第 i 个记录进行互换。如图所示。时间性能：对n个记录的关键字进行简单选择排序，所需进行的关键字比较次数总计为移动记录的次数最小值为0，最大值为3(n-1)时间复杂度为O（n2）选择排序的主要操作是进行关键字的比较，改进简单选择排序应从如何减少比较次数出发考虑。即利用前次比较信息减少以后各趟选择排序中所比较次数。就可以提高选择排序的效率。如体育比赛中的锦标赛便是一种选择排序（树型选择排序）。如：8个运动员中决出前3名至多需要11场比赛 由于含有n个结点的二叉树的深度为log2n+1则在树型选择排序中，除了最小关键字外，没选择一个次小关键字仅需要进行log2n次比较，因此，它的时间复

18、杂度为O（nlogn），但是这种排序方法所需辅助空间较多，和最大值进行多余的比较等缺点。威洛姆斯（J.willioms）在1964年提出了另一种形式的选择排序堆排序。10.4.2 堆排序 何谓“堆”？堆是满足下列性质的n个元素的序列k1,k2,kn满足下列关系则称作小顶堆 或大顶堆“堆顶”元素为序列中的“最小值”或“最大值“小顶堆大顶堆 利用堆的特性进行的排序方法即为“堆排序”其排序过程如下：假设待排关键字序列为：34,39,20,65,47,12,98,73,81,56 1）先将它调整为大顶堆：98,81,34,73,56,12,20,39,65,47 2）互换“堆顶”和待排序列中 的最后的

19、关键字：47,81,34,73,56,12,20,39,65,98 3）在待排序列中舍去最大关键字，将其余部 分重新调整为堆 81,73,34,65,56,12,20,39,47 98 4）重复2）和3）直至待排序列中只剩一个关键字为止。可见，堆排序的两个关键问题是：1）如何将一个无序序列调整为堆？2）如何在互换堆顶之后重新调整为堆？先讨论第二个问题:只要“从上到下”进行“筛选”可将该序列重新调整为大顶堆。如动画flash10-4-2如何建堆？建堆的过程是一个从下到上调整堆的过程。例如动画 flash10-4-4所示对无序序列进行建堆的过程。教材p282 算法10.10 调整堆的过程教材p28

20、2 算法10.11 堆排序过程堆排序的时间复杂度分析 1）对深度为k的堆，筛选所进行的关键字比较的次数至多为2(k-1)。2）对n个关键字建成深度为h的堆，所需进行的关键字比较的次数至多为4(n)。3）调整堆顶n-1次，总共进行的关键字比较次数不超过堆排序的时间复杂度为O(nlogn)10.5 归并排序法 10.5.1 2-路归并排序 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列 如动画flash10-5-2所示void MSort(RcdType SR,RcdT

21、ype TR1,int s,int t)/将SRs.t归并序列为TR1s.tif(s=t)TR1s=SRs;else m=(s+t)/2;/将SRs.t平分为和SRm+1.t MSort(SR,TR2,s,m);/递归的将SRs.m归并为有序的TR2s.m MSort(SR,TR2,m+1,s);/递归的将SRm+1.t归并为有序的TR2m+1.t Merge(TR2,TR1,s,m,t);/将TR2s.mTR2m+1.t归并到TR1s.t/else/MSortvoid MergSort(SqList&L)/对顺序表L作归并排序 MSort（L.r，L.r,1,L.length）;/MergS

22、ort10.6 基数排序 10.6.1 多关键字的排序 一般情况下，对多关键字排序的定义为：假设含有n个记录的序列为：（R1,R2,Rn）每个记录Ri中含有d个关键字(Ki0,Ki1,Kid-1)则称该记录序列对关键字(Ki0,Ki1,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj（1ijn）都满足下列有序关系(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中K0为最主位关键字，Kd-1为最次位关键字。假如你手中有一副扑克牌，若要将它们排列成一个有序序列，你准备怎么做？通常实现多关键字排序可以有两种策略：一是最主位优先主位优先（MSD法）一是最次位优先最次位优先（LSD法

23、）你可能是先按不同“花色”分成有次序的四堆，然后分别对每一堆按“面值”大小（23A）排列有序。若将花色视作K0，将面值视作K1，这种整理方法即为MSD的作法。例如，对含（系别、班号和班内序列号）三个关键字的记录序列按“最低位优先”进行排序。过程 如动画flash10-6-1所示 10.7 各种排序方法的综合比较 一、时间性能 1.按平均的时间性能来分，有三类排序方法：时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序时间复杂度为O(n2)的有：插入排序、起泡排序和选择排序，时间复杂度为O(n)的排序方法只有基数排序一种。其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在

24、 n 值较大的情况下，归并排序较堆排序更快；其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少 2.当待排记录序列按关键字顺序有序时，插入排序和起泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此应尽量避免。3.选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。4.以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过

25、程中占的比例更大，从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小。1.所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O(1)。2.快速排序为O(logn)，为递归程序执行过程中栈所需的辅助空间。3.归并排序和基数排序所需辅助空间最多，其空间复杂度为O(n)。三、排序方法的稳定性能三、排序方法的稳定性能1.稳定的排序方法指的是，对于两个关键字相等的记录在经过排序之后，不改变它们在排序之前在序列中的相对位置。2.除希尔排序、快速排序和堆排序是不稳定的排序方法外，本章讨论的其它排序方法都是稳定的。3.稳定

26、性是由方法本身决定的。综合上述，可得右侧列表结果 本章小结 本章主要讨论各种内部排序的方法。一般来说，在选择排序方法时，可有下列几种选择：1)若待排序的记录个数n值较小，则可选用插入排序，若记录所含数据项较多，存储量大，应选用选择排序 若待排序的记录个数n值较大时，应选用快速排序。但若待排序记录关键字有有序倾向时，就慎用快速排序，宁可选用堆排序或归并排序，而后两者的最大差别是所需辅助空间不等。2)快速排序和归并排序在n值较小时的性能不及直接插入排序，因此在实际应用时，可将它们和插入排序“混合”使用。3)基数排序的时间复杂度为O(dn)，因此特别适合于待排记录数 n 值很大，而关键字“位数 d”较小的情况。并且还可以调整“基数”（如将基数定为100或1000等）以减少基数排序的趟数d的值。4)一般情况下，对单关键字进行排序时，所用的排序方法是否稳定无关紧要。但当按最次位优先进行多关键字排序时(除第一趟外)必须选用稳定的排序方法。课后习题 以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序；(2)希尔排序(增量 d1=5)；(3)快速排序；(4)堆排序；(5)归并排序；(6)基数排序。