【教学课件】第十章内部排序.ppt

《【教学课件】第十章内部排序.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第十章内部排序.ppt（43页珍藏版）》请在三一办公上搜索。

1、第十章 内部排序,基本概念 插入排序 快速排序 选择排序 归并排序 基数排序,10.1 基本概念,设含有n个记录的文件R1,R2,.,Rn，其相应的关键字为K1,K2,.,Kn，将记录按关键字值非递减(或非递增)顺序排列的过程，称为排序。对所有的Ki=Kj(ij),若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方法是稳定的，反之，称为不稳定 的。稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。,10.1 基本概念,内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排

2、序。,10.1 基本概念,内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2)先进排序 O(nlogn)基数排序 O(dn),10.2 插入排序,一.直接插入排序(最简单的排序方法）基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1)例如：已有待排序文件为：38，65，49，76，97 首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到有序文件的合适位置。,10.2 插入排序,直接插入排序算法 PROC strainsort(VAR r

3、:filetype)；FOR i:=2 TO n DO r0:=ri;j:=i-1;r1ri-1为有序子文件 WHILE r0.keyrj.key DO rj+1:=rj;j:=j-1;确定插入位置并移动 rj+1:=r0 ENDP;strainsort,10.2 插入排序,算法分析 空间上，只需i，j两个整型变量和一个记录的辅助空间r0,r0作为“监视哨”，控制待插入元素相对于有序子文件为最小时WHILE循环的结束，同时也用于暂存待插入元素。时间上，只包含比较关键字和移动记录两种操作。比较次数:1/.当待初始文件按关键字递增有序(正序)时：a.对每个记录只进行一次比较，整个排序过程共 n进行

4、了1=n-1次比较(最少)；i=2 b.每个记录都要进行ri移到r0和r0移到rj+1两次移动，因此共移动2(n-1)次(最少)。,10.2 插入排序,2/.当待排序文件按关键字非递增有序(逆序)时 记录ri(i=2,3,.n)均要和前i-1个记录及r0进行比较，整个排序过程共进行了 n i=(n+2)(n-1)/2次比较(最多)；i=2 移动记录次数：每个记录都要进行ri移动到r0和r0移动到rj+1两次移动，另外当ri.keyrj.key时，还将rj移动到rj+1，所以，当初始文件为正序时，移动记录次数最少为2（n-1）次，当初始文件为逆序时移动记录次数最多为 n(i-1)+2(n-1)=

5、(n+4)(n-1)/2次(最多)。i=2,10.2 插入排序,结论 1/.直接插入排序的效率与待排文件的关键字排列有关；2/.直接插入排序的时间复杂度为O(n2)；3/.直接插入排序是稳定的(这一点由过程中WHILE语句的条件“”保证的)。,PROC strainsort(VAR r:filetype)；FOR i:=2 TO n DO r0:=ri;j:=i-1;WHILE r0.keyrj.key DO rj+1:=rj;j:=j-1;rj+1:=r0 ENDP;strainsort,10.2 插入排序,二.折半插入排序 由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入

6、排序法中的顺序查找，从而可减少比较次数。,10.2 插入排序,PROC binsort(VAR r：listtype)；FOR i：=2 TO n DO s：=1；j：=i-1；r0：=ri；WHILE sj DO m：=（s+j）/2；IF rikeyrmkey 确保稳定，若改为，则不稳定 THEN j：-1 ELSE s：=m+1；FOR k：=i-1 DOWNTO j+1 DO rk+1：=rk；rj+1：=r0 ENDP；binsort 移动次数未变，故仍为O(n2),10.2 插入排序,WHILE sj DO m：=（s+j）/2；IF rikeyrmkey 确保稳定，若改为，则不稳

7、定 THEN j：-1 ELSE s：=m+1；,10.2 插入排序,三.希尔排序（Shells Methool）(又称为缩小增量排序)基本思想：分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。依据：若待排序文件基本有序，即文件中具有特性：ri.key Max rj 1ji的记录数较少，则文件中大多数记录都不需要进行插入。基本有序时，直接插入排序效率可以提高，接近于O(n)。,10.2 插入排序,例：设初始关键字为：49 38 65 97 76 13 27 49 55 04第一趟以步长为5分割为5个子文件：(R1,R6)(R2

8、,R7)(R3,R8)(R4,R6)(R5,R10)，对每个子文件进行直接插入排序结果为：13 27 49 55 04 49 38 65 97 76第二趟以步长为3对第一趟排序结果分割为3 个子文件：(R1,R4,R7,R10)(R2,R5,R8)(R3,R6,R9)对每个子文件进行直接插入排序，结果为：13 04 49 38 27 49 55 65 97 76 第三趟以步长为1对第二趟排序结果进行直接插入排序，结果为：04 13 27 38 49 49 55 65 76 97,10.2 插入排序,4希尔排序的特点 子文件（子序列）的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成

9、一个子文件。增量序列应是递减，且最后一个必须为1。希尔排序法是不稳定的。,5.希尔排序算法的实现PROC shellsort(VAR r:ARRAY-d1:n OF rcdtype；d:ARRAY1.t OF integer)；d1.dt为增量序列，r(-d1.n)中,-d1.0为各趟监视哨位，1.n为记录 k:=1;REPEAT dh:=dk;s:=-dh+1;s为哨兵位,dh为增量值 FOR i:=dh+1 TO n DO rs:=ri;j:=i-dh;WHILE rs.keyrj.key DO rj+dh:=rj;j:=j-dh;rj+dh:=rs;s:=s+1;IF s0 THEN s

10、:=-dh+1;k:=k+1 UNTIL dh=1ENDP;shellsort,10.2 插入排序,k:=1;REPEAT dh:=dk;s:=-dh+1;FOR i:=dh+1 TO n DO rs:=ri;j:=i-dh;WHILE rs.keyrj.key DO rj+dh:=rj;j:=j-dh;rj+dh:=rs;s:=s+1;IF s0 THEN s:=-dh+1;k:=k+1 UNTIL dh=1,10.2 插入排序,10.3 快速排序,快速排序是目前内部排序中最快的方法。基本思想：选取某个记录，（通常选文件的第一个记录），将所有关键字不大于它的记录放在它的前面，将所有关键字不小

11、于它的记录放在它的后面，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。,具体步骤(1)置变量i，j初值分别为文件的首、尾记录位置；选取文件首记录ri，并将其关键字赋给变量x；(2)从j 位置开始向前搜索，(3)直到遇到第一个关键字小于x的记录，(4)并将rj移至ri；(5)从i 位置开始向后搜索，(6)直到遇到第一个关键字大于x的记录，(7)并将ri移至rj；(8)重复(2)(9)直到i=j，(10)并将x移至ri，以ri为中枢将文件分为r1.i-1和ri+1.n两部分，完成一趟排序；(11)重复(1)至(10)，直到每一部分只剩上一

12、个记录，整个文件已有序，快速排序算法结束。,10.3 快速排序,3.示意图：,注意：向前搜索时，j：=j-1，且ri空闲；向后搜索时，i：=i-1，且rj空闲。,10.3 快速排序,一趟快速排序算法 PROC qkpass(VAR r:listtype;s,t:integer;VAR i:integer);对rs.t进行一趟快速排序,i将rs.t分为两部分 rsi-1的关键字不大于ri.key,ri+1t的关键字不小于ri.key i:=s;j:=t;rp:=rs;x:=rs.key;WHILE ij DO WHILE(ij)AND(rj.keyx)DO j:=j-1;ri:=rj;WHILE

13、(ij)AND(ri.keyx)DO i:=i+1;rj:=ri ri:=rp ENDP;qkpass,10.3 快速排序,例如：x初始关键字 49 38 65 97 76 13 27 49 i j 27 i 65 13 i 97完成一趟排序（27 38 13）49（76 97 65 49)（13）27（38）（49 65）76(97)结束 结束 49(65)结束 结束最后（13 27 38 49 49 65 79 97）,10.3 快速排序,快速排序算法特点 快速排序算法是不稳定的。对待排序文件 49 49 38 65，快速排序结果为:38 49 49 65 快速排序的效率跟初始文件中关键字

14、的排列和选取划分的记录有关。当初始文件按关键字有序(正序或逆序)时，性能最差，时间复杂度为O(n2)；常用“三者取中”法来选取划分记录，即取首记录rs.key.尾记录rt.key和中间记录r(s+t)/2.key三者的中间值为划分记录。(4)快速排序算法的平均时间复杂度为O(nlogn)。,10.4 选择排序,一.简单选择排序 基本思想：对文件进行n-1趟排序，第i趟(i=1,2,.n-1)是在从i到 n的n-i+1个记录中选择关键字最小的记录，并将它与第i个记录进行交换。,第一趟 n个记录第二趟 n-1 第-1趟 2,比较次数n-1n-21,10.4 选择排序,简单选择排序算法 PROC s

15、mp-selecsort(VAR r:listtype);FOR i:=1 TO n-1 DO k:=i;FOR j:=i+1 TO n DO IF rj.keyrk.key THEN k:=j;IF ki THEN rirk ENDP;smp-selecsort,10.4 选择排序,算法分析 交换次数：正序时交换次数最少，为0次，逆序时最多，为n-1次。比较次数：与初始文件关键字排列无关，为n(n-1)/2次。简单选择排序时间复杂度为O(n2)，并且是稳定的排序。,10.4 选择排序,10.4 选择排序,若将堆视为一个完全二叉树（图一），则堆的含义为：完全二叉树中所有非终端结点的值均不大于(

16、或不小于)其左、右孩子的值（图二）。堆顶元素(即完全二叉树的根)是序列中最小(或最大)的元素。,10.4 选择排序,堆排序基本思想 以初始关键字序列，建立堆；输出堆顶最小元素；调整余下的元素，使其成为一个新堆；重复,n 次，得到 一个有序序列。关键要解决和，即如何由一个无序序列建成一个堆?如何调整余下的元素成为一个新堆?,10.4 选择排序,调整方法 将堆顶元素和堆的最后一个元素位置交换；然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较小的结点进行交换；重复，继续调整被交换过的子树，直到叶结点或没进行交换为止。称这个调整过程为筛选。,10.4 选择排序,例：

17、,10.4 选择排序,10.4 选择排序,筛选过程PROC shift(VAR r:listtype;k,m:integer);已知 vk.m是以rk为根的完全二叉树,以r2k和r2k+1 为根的左、右子树是堆。要求:调整rk使rk.m为堆 i:=k;j:=2*i;x:=rk.key;t:=rk;finished:=false;WHILE(jm)AND NOT finished DO IF(jm)AND(rj.keyrj+1.key)THEN j:=j+1;满足条件,沿右枝筛选 IF xrj.key THEN finished:=true ELSE ri:=rj;i:=j;j:=2*i ri:

18、=t ENDP;sift,10.4 选择排序,无序序列建堆过程 方法：从完全二叉树的最后一个非终端结点 n/2开始，反复调用筛选过程，直到第一个结点，则得到一个堆。,例：49，38，65，97，76，13，27，49,10.4 选择排序,堆排序过程 PROC headsort(VAR r:listtype);FOR i:=n/2 DOWNTO 1 DO shift(r,i,n);自第 n/2开始筛选建堆 FOR i:=n DOWNTO 2 DO r1ri;堆顶与堆中最后一个记录交换 shift(r,1,i-1)使r1.i-1成为堆 ENDP;headsort堆排序是不稳定的，时间复杂度为O(n

19、logn)。,10.5 归并排序,归并概念：把 2 个有序子文件合并成一个有序文件的过程，称为2-路归并。归并排序基本思想：将文件的每个记录视为一个有序子文件；然后两两子文件进行2-路归并；重复，直到只剩一个长度为n的有序文件 例：初始关键字：49 38 65 97 76 13 27 49 第一趟后 38 49 65 97 13 76 27 49第二趟后 38 49 65 97 13 27 49 76第三趟后 13 27 38 49 49 65 76 97 每个记录视为一个有序子文件，两个子文件进行归并，得4个有序子文件。,归并排序过程 PROC merge(r:listtype;l,m,n:

20、integer;VAR r2:listtype);ts.m和rm+1.n 为两个有序子文件,归并结果存放在r2s.n中 i:=s;j:=m+1;k:=s-1;WHILE(im)AND(jn)DO k:=k+1;k为下一次存入r2的位置 IF ri.keyrj.key THEN r2k:=ri;i:=i+1 ELSE r2k:=rj;i:=j+1;IF im THEN r2k+1.n:=ri.m;IF jn THEN r2k+1.n:=rj.n 将其中一个文件的余下部分复制到r2的尾部 ENDP;merge,归并排序是稳定的，时间复杂度为O(nlogn)，需要和待排序记录相等数量的辅助空间r2。

21、,10.6 基数排序,基数排序法是一种用多关键字排序思想对单逻辑关键字进行排序，而无需进行关键字比较的新排序方法，其基本操作是“分配”和“收集”。基数排序方法：基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。设关键字有d 位，每位的取值范围为 r(称为基数)，则需要进行d 趟分配与收集，需要设立 r 个队列。例如，若每位是十进制数字，则需要设立10个队列，若每位由小写字母组成，则要设立26个队列。,10.6 基数排序,2.基数排序的步骤 从关键字的低位开始进行第i趟(i=1,2,.d)分配即将单链表中的记录依次按关键字的第i位分配到相应编号的队列中；分配完毕后，将各队列的记录按队列编号顺序收集成一个单链表；重复，直到第d趟收集完毕，所得单链表已成为有序表。,10.6 基数排序,10.6 基数排序,基数排序的特点 基数排序的基本操作是分配和收集，而不是关键字之间的比较；基数排序是稳定的，其时间复杂度为O(d(n+rd)，其中n是记录数，d是关键字的位数，r是关键字各位的值域。基数排序要进行d趟分配和收集,需r个队列,