考研数据结构chapt10

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第十章 内部排序,基本概念,插入排序,快速排序,选择排序,基数排序,1,10.1,基本概念,设含有n个记录的文件R,1,R,2,.,R,n,，其相应的关键字为K,1,K,2,.,K,n,，将记录按关键字值非递减(或非递增)顺序排列的过程，称为,排序,。,对所有的K,i,=K,j,(ij),若排序前R,i,领先于R,j,排序后R,i,仍领先于R,j,则称该排序方法是,稳定的,，反之，称为,不稳定,的。,稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。,2,10.1,基本概念,内部排序,：待排序文件的全部记录存放在内存进行的排序，称为内部排序。,外部排序,：排序过程中需要进行内外存数据交换的排序，称为外部排序。,3,10.1,基本概念,内排序分类,按排序过程依据的原则分为：插入排序,交换排序,选择排序,归并排序,计数排序,按排序过程所需的工作量分：简单排序 O(n,2,),先进排序 O(nlog,n,),基数排序 O(dn),4,10.2 插入排序,一. 直接插入排序,(最简单的排序方法）, 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1),例如：已有待排序文件为：38，65，49，76，97,首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到有序文件的合适位置。,5,10.2 插入排序, 直接插入排序算法,PROC strainsort(VAR r:)；,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,6,10.2 插入排序, 算法分析, 空间上,，只需i，j两个整型变量和一个记录的辅助空间r0, r0作为“监视哨”，控制待插入元素相对于有序子文件为最小时WHILE循环的结束，同时也用于暂存待插入元素。, 时间上,，只包含比较关键字和移动记录两种操作。,比较次数 :,1/. 当待初始文件按关键字递增有序(正序)时：,a.对每个记录只进行一次比较，整个排序过程共,n,进行了1=n-1次比较(最少)；,i=2,b.每个记录都要进行ri移到r0和r0移到rj+1两次移动，因此共移动2(n-1)次(最少)。,7,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)=(n+4)(n-1)/2次(最多)。,i=2,8,10.2 插入排序, 结论,1/. 直接插入排序的效率与待排文件的关键字排列有关；,2/. 直接插入排序的时间复杂度为O(n,2,)；,3/. 直接插入排序是稳定的(这一点由过程中WHILE语句的条件“”保证的)。,PROC strainsort(VAR r:)；,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,9,10.2 插入排序,二. 折半插入排序,由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，从而可减少比较次数。,10,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(n,2,),11,10.2 插入排序,s j,m,j s(m),s.j,s .j.m,j s. m,j. m.s,WHILE sj DO,m：=（s+j）/2 ；,IF rikeyrmkey,确保稳定，若改为，则不稳定,THEN j：-1 ELSE s：=m+1；,12,10.2 插入排序,三. 希尔排序（Shells Methool）(又称为缩小增量排序),基本思想,：分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。,依据,：若待排序文件基本有序，即文件中具有特性：,ri.key Max rj 1ji的记录数较少，,则文件中大多数记录都不需要进行插入。,基本有序时，直接插入排序效率可以提高，接近于O(n)。,13,10.2 插入排序,例,：设初始关键字为：49 38 65 97 76 13 27 49 55 04,第一趟以步长为5分割为5个子文件：(R1,R6) (R2,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,14,10.2 插入排序,4希尔排序的特点, 子文件（子序列）的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子文件。, 增量序列应是递减，且最后一个必须为1。, 希尔排序法是不稳定的。,15,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:= -dh+1 ;,k:=k+1 ,UNTIL dh=1,ENDP; shellsort,16,k dh i s j -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10,1 5 6 -4 1 13 49 38 65 97 76 13 27 49 55 04,-4 while 49,13,FOR 7 -3 2 while 27 38,-3 27,8 -2 3 while 49,-2 49 97,9 -1 -4 while 55,-1 55,10 0 5 while 04 76,0 04,交换5次,13 27 49 55 04 49 38 65 97 76,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,17,10.2 插入排序,k dh i s j -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10,1 5 6 -4 1 13 49 38 65 97 76 13 27 49 55 04,-4 while 49,13,FOR 7 -3 2 while 27 38,-3 27,8 -2 3 while 49,-2 49 97,9 -1 -4 while 55,-1 55,10 0 5 while 04 76,0 04,交换5次,13 27 49 55 04 49 38 65 97 76,2 3 4 -2 1 while 55,5 -1 2 while 04 27,-1 04,6 0 3 while 49,7 1(-2) 4 while 38 55,-2 38,8 -1 5 while 65,9 0 6 while 97,10 1(-2) 7 while 76,交换2次,1 13 04 49 38 27 49 55 65 97 76,共交换12次 04 13 49 38 27 49 55 65 97 76,18,10.3 快速排序,快速排序是目前内部排序中最快的方法。, 基本思想,：选取某个记录，（通常选文件的第一个记录），将所有关键字不大于它的记录放在它的前面，将所有关键字不小于它的记录放在它的后面，这样遍历一趟文件后，将文件以该记录为界分为两部分，然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。,19, 具体步骤,(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)，直到每一部分只剩上一个记录，整个文件已有序，快速排序算法结束。,20,10.3 快速排序,3. 示意图：,x,5,向后搜索,rikeyx,i=j,7,ri rj,rjkeyx,向前搜索,2,j,3,rj,key,x,8,4,rj ri,rikeyx,6,9,10,x ri,1,x,1,x i-1 i i+1 x n,注意：向前搜索时，j：=j-1，且ri空闲；,向后搜索时，i：=i-1，且rj空闲。,21,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 (ij) AND (ri.keyx) DO i:=i+1;,rj:=ri,ri:=rp,ENDP; qkpass,22,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）,23,10.3 快速排序, 快速排序算法特点, 快速排序算法是不稳定的。,对待排序文件 49 49 38 65，,快速排序结果为: 38 49 49 65, 快速排序的效率跟初始文件中关键字的排列和选取划分的记录有关。当初始文件按关键字有序(正序或逆序)时，性能最差，时间复杂度为O(n,2,)；,常用“三者取中”法来选取划分记录，即取首记录rs.key.尾记录rt.key和中间记录r(s+t)/2.key三者的中间值为划分记录。,(4)快速排序算法的平均时间复杂度为O(nlogn)。,24,10.4 选择排序,一.简单选择排序, 基本思想,： 对文件进行n-1趟排序，第i趟(i=1,2,.n-1)是在从i到 n的n-i+1个记录中选择关键字最小的记录，并将它与第i个记录进行交换。,1 n,第一趟 n个记录,第二趟 n-1, ,第-1趟 2,比较次数,n-1,n-2,1,25,10.4 选择排序, 简单选择排序算法,PROC smp-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,26,10.4 选择排序, 算法分析, 交换次数：正序时交换次数最少，为0次，,逆序时最多，为n-1次。, 比较次数：与初始文件关键字排列无关，,为n(n-1)/2次。, 简单选择排序时间复杂度为O(n,2,)，,并且是稳定的排序。,27,10.4 选择排序,二. 堆排序, 堆的定义,：n个元素的序列K,1,K,2,.,K,n,若满足： K,i,K,2i,或 K,i,K,2i,K,i,K,2i,+1,K,i,K,2i+1,(i=1, 2,. n/2),称为堆。,28,10.4 选择排序,若将堆视为一个完全二叉树（图一），则堆的含义为：完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子的值（图二）。堆顶元素(即完全二叉树的根)是序列中最小(或最大)的元素。,k,3,k,1,k,5,k,2,k,4,图一,24,12,47,38,85,91,30,53,图二,29,10.4 选择排序, 堆排序基本思想, 以初始关键字序列，建立堆；, 输出堆顶最小元素；, 调整余下的元素，使其成为一个新堆；, 重复, n 次，得到 一个有序序列。,关键要解决和，即如何由一个无序序列建成一个堆? 如何调整余下的元素成为一个新堆?,30,10.4 选择排序, 调整方法, 将堆顶元素和堆的最后一个元素位置交换；, 然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较小的结点进行交换；, 重复，继续调整被交换过的子树，直到叶结点或没进行交换为止。,称这个调整过程为筛选。,31,10.4 选择排序,例：,27,13,76,38,49,97,65,49,输出13,27,97,76,38,49,13,65,49,筛选,49,27,76,38,49,13,65,97,筛选结果,输出27,32,49,97,76,38,49,13,65,27,1,2,49,38,76,49,97,13,65,27,10.4 选择排序,33,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:=t,ENDP; sift,34,10.4 选择排序, 无序序列建堆过程,方法：从完全二叉树的最后一个非终端结点,n/2,开始，反复调用筛选过程，直到第一个结点，则得到一个堆。,35,13,49,76,38,49,97,65,27,65,49,76,38,97,49,13,27,27,13,76,38,49,97,65,49,例：,49，38，65，97,，76，13，27，49,36,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(nlogn)。,37,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个有序子文件。,38, 归并排序过程,PROC merge(r:listtype; l,m,n: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。,39,10.6 基数排序,基数排序法是一种用多关键字排序思想对单逻辑关键字进行排序，而无需进行关键字比较的新排序方法，其基本操作是“分配”和“收集”。, 基数排序方法,：基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。,设关键字有d 位，每位的取值范围为 r (称为基数)，则需要进行d 趟分配与收集，需要设立 r 个队列。例如，若每位是十进制数字，则需要设立10个队列，若每位由小写字母组成，则要设立26个队列 。,40,10.6 基数排序,2. 基数排序的步骤, 从关键字的低位开始进行第i趟(i=1,2,.d)分配即将单链表中的记录依次按关键字的第i位分配到相应编号的队列中；, 分配完毕后，将各队列的记录按队列编号顺序收集成一个单链表；, 重复，直到第d趟收集完毕，所得单链表已成为有序表。,41,10.6 基数排序,例：,初始,278109063930589184505269008083,0 1 2 3 4 5 6 7 8 9,第一趟分配 269,083 008 589,930 063 184 505 278 109,第一趟收集,930063083184505278008109589269,第二趟分配 109 589,008 269 184,505 930 063 278 083,第二趟收集,505008109930063269278083184589,第三趟分配 083,063 184 278 589,008 109 269 505 930,第三趟收集,008063083109184269278505589930,42,10.6 基数排序, 基数排序的特点, 基数排序的基本操作是分配和收集，而不是关键字之间的比较；, 基数排序是稳定的，其时间复杂度为O(d(n+rd)，其中n是记录数，d是关键字的位数，r是关键字各位的值域。, 基数排序要进行d趟分配和收集,需r个队列,43,