《数据结构》课件第9章(内排序).ppt

1、 排序：排序：设含有设含有n个记录的文件个记录的文件R1,R2,，Rn,其其 相应的关键字为相应的关键字为K1,K2,，Kn，需确定，需确定 一种排列一种排列P(1),P(2),P(n),使其相应的关键使其相应的关键 字满足如下的递增字满足如下的递增(或递减或递减)关系：关系：KP(1)KP(2)KP(3)KP(n)即，使上述文件成为一个按其关键字线性即，使上述文件成为一个按其关键字线性 有序的文件有序的文件RP(1),RP(2),，RP(n),这样一这样一 种运算称为排序。种运算称为排序。基本概念基本概念排序的稳定性：排序的稳定性：如果在排序期间具有相同关键字如果在排序期间具有相同关键字的记

2、录的相对位置不变，则称此方法是稳定的。的记录的相对位置不变，则称此方法是稳定的。即，即，1)K(i)K(i+1)(1 i n-1)i n-1)2)2)若在输入文件中若在输入文件中ij,irj.key then ri.count:=ri.count+1;else rj.count:=rj.count+1;For i:=1 to n-1 Do j:=i;while rj.counti Do j:=j+1;if i j then call exchange(ri,rj);End;算法性能分析：算法性能分析：设文件有设文件有n个记录，则外循环：个记录，则外循环：i=1时，内循环要做时，内循环要做n-1

3、次比较；次比较；i=2时，内循环要做时，内循环要做n-2次比较；次比较；i=n-1时，内循环要做时，内循环要做1次比较；次比较；总的比较次数为总的比较次数为(n-1)+(n-2)+1=n(n-1)/2所以，算法所需时间为所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，由于不需要记录移动和额外空间，同时算法简单，当同时算法简单，当n较小时，可采用本算法。较小时，可采用本算法。直接插入排序直接插入排序假设在排序过程中，记录序列假设在排序过程中，记录序列R1.nR1.n的状态为：的状态为：则一趟插入排序的基本思想为：将记录则一趟插入排序的基本思想为：将记录RiRi插入到有插入到有序子序

4、列序子序列R1.i-1R1.i-1中，使记录的有序序列从中，使记录的有序序列从R1.i-R1.i-11变为变为R1.iR1.i。显然，完成这个显然，完成这个“插入插入”需分三步进行：需分三步进行：1 1查找查找RiRi的插入位置的插入位置j+1j+1；2 2将将Rj+1.i-1Rj+1.i-1中的记录后移一个位置；中的记录后移一个位置；3 3将将RiRi复制到复制到Rj+1Rj+1的位置上。的位置上。直接插入排序直接插入排序：利用顺序查找实现利用顺序查找实现“在在R1.i-1中查找中查找Ri的插入位置的插入位置”的插入排序。的插入排序。注意直接插入排序算法的三个要点：注意直接插入排序算法的三个

5、要点：1.1.从从Ri-1起向前进行顺序查找，监视哨设置在起向前进行顺序查找，监视哨设置在R0R0；R0:=Ri；设置设置“哨兵哨兵”j:=i-1;while(R0.keyRj.key)Do j:=j-1;/从后往前找从后往前找 Return(j+1);返回返回Ri的插入位置为的插入位置为j+12.2.对于在查找过程中找到的那些关键字不小于对于在查找过程中找到的那些关键字不小于Ri.key的记录，并的记录，并 在查找的同时实现记录向后移动；在查找的同时实现记录向后移动；while(R0.keyRj.key)Do Rj+1:=Rj;j:=j-1;3.i=23.i=2，3 3，,n,n,实现整个序

6、列的排序。实现整个序列的排序。排序算法如下：排序算法如下：Procedure insort(var r:List;n:Integer);Begin 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;End;排序的时间分析：排序的时间分析：实现排序的基本操作有两个：实现排序的基本操作有两个：（1 1）“比较比较”序列中两个关键字的大小；序列中两个关键字的大小；（2 2）“移动移动”记录。记录。对于直接插入排序：对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记

7、录序列中顺序有序）：“比较比较”的次数：的次数：“移动移动”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较比较”的次数：的次数：“移动移动”的次数：的次数：总的说来，直接插入排序所需进行关键字间的比较次数和记录移总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为动的次数均为n n2 2/4/4，所以直接插入排序的时间复杂度为，所以直接插入排序的时间复杂度为O(nO(n2 2)。2(n-1)折半插入排序折半插入排序排序算法的思想：排序算法的思想：由于直接插入排序的内循环由于直接插入排序的内循环(从从1到到i-1)的查找

8、的查找(或说是比较或说是比较)是在是在(部分部分)有序表的环境下进行的，有序表的环境下进行的，所以内循环用所以内循环用“折半查找法折半查找法”，比用顺序查找法快。，比用顺序查找法快。算法描述如下：算法描述如下：Procedure binsort(var r:List;n:Integer);Begin For i:=2 to n Do r0:=ri;l:=1;h:=i-1;while l=h Do m:=(l+high)div 2;if r0.keyrm.key then h:=m-1 else l:=m+1;For j:=i-1 DownTo l Do rj+1:=rj;rl:=r0;End;

9、表插入排序表插入排序 为了减少在排序过程中进行的为了减少在排序过程中进行的“移动移动”记录的操作记录的操作，必须改变排序过程中采用的存储结构。利用静态链，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。应该在的位置上。例如例如:算法描述如下：算法描述如下：Procedure Linsertion_Sort(r:List;n:Integer);Begin r0.key=MAXINT;r0.next=1;

10、r1.next=0;For i:=2 to n Do j:=0;k:=r0.next;while(rk.key=ri.key)and(k0)Do j:=k;k:=rk.next;rj.next=i;ri.next=k;结点结点i插入在结点插入在结点j和结点和结点k之间之间 End;从表插入排序的过程可以看出，它的基本操作仍是将一个记从表插入排序的过程可以看出，它的基本操作仍是将一个记录插入到已排序好的有序表中。和直接插入排序相比，不同之处录插入到已排序好的有序表中。和直接插入排序相比，不同之处仅是以修改仅是以修改2n次指针值代替移动记录，排序的过程中所需进行的次指针值代替移动记录，排序的过程中

11、所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂性仍是关键字间的比较次数相同。因此，表插入排序的时间复杂性仍是O(n2)。另一方面，表插入排序的结果只是求得了一个有序链表，则只另一方面，表插入排序的结果只是求得了一个有序链表，则只能对它进行顺序查找，不能进行随机查找，为了能应用有序表的能对它进行顺序查找，不能进行随机查找，为了能应用有序表的折半查找，需对记录进行重新排列。折半查找，需对记录进行重新排列。重排记录的做法是：顺序扫描有序链表，将链表中第重排记录的做法是：顺序扫描有序链表，将链表中第i个结点个结点移动至数组的第移动至数组的第i个分量中。它的做法是：若第个分量中。它的做法是

12、：若第i个最小关键字的结个最小关键字的结点是数组中下标为点是数组中下标为p且且pi的分量，则互换的分量，则互换ri和和rp，且令，且令ri中指中指针域的值改为针域的值改为p;由于此时数组中所有小于由于此时数组中所有小于i的分量已是到位的记录，的分量已是到位的记录，则当则当p=i时为止。时为止。算法描述如下：算法描述如下：Procedure Arrange(var r:stlisttp);本算法根据本算法根据r0.n中个分量指针域的值调整中个分量指针域的值调整r1.n中记录，使数中记录，使数 组中各分量中的记录按关键字非递减有序顺序排列组中各分量中的记录按关键字非递减有序顺序排列Begin i:

13、=1;p:=r0.next;while i=n-1 Do while pi Do p:=ri.next;p指示第指示第i个结点在当前数组中的位置个结点在当前数组中的位置 q:=rp.next;if pi then t:=rp;rp:=ri;ri:=t;ri.next:=p;交换记录并保持指向交换记录并保持指向rp中记录的指针中记录的指针 i:=i+1;p:=q;End;冒泡排序冒泡排序排序算法的思想：排序算法的思想：比较比较k k1 1和和k k2 2,如果这些关键字的值不符合排序顺如果这些关键字的值不符合排序顺序序,就交换就交换k k1 1和和k k2 2；然后对记录；然后对记录k k2 2

14、和和k k3 3,k,k3 3和和k k4 4等等进行相同的工等等进行相同的工作。作。直到直到k kn-1n-1和和k kn n为止为止,到此得到一个最大到此得到一个最大(或最小或最小)关键字值存关键字值存在在k kn n的位置上的位置上(通常将此过程叫做一趟通常将此过程叫做一趟)。重复这个过程。重复这个过程,就得到在就得到在位置位置kn-1,kn-2kn-1,kn-2等处的适当记录等处的适当记录,使得所有记录最终被排好序。使得所有记录最终被排好序。7 4 4 3 34 7 3 4 4 8 3 7 7 73 8 8 8 89 9 9 9 9 例如例如:将将5 5个记录的关键字个记录的关键字7,

15、4,8,3,97,4,8,3,9进行冒泡排序。排序后进行冒泡排序。排序后k1k2k1k2kn(n=5)kn(n=5)。因为到第四趟就没有交因为到第四趟就没有交换的偶对了换的偶对了,所以整个排序所以整个排序结束。结束。算法描述如下算法描述如下Procedure Bubble_sort(var r:List;n:Integer);Begin For m:=1 to n Do read(rm);k:=n;Repeat all:=True;For m:=1 to k-1 Do i:=m+1;if rmri then max:=rm;rm:=ri;ri:=max;all:=false k:=k-1;Un

16、til(all=True)or(k=1);End;冒泡排序的结束条件为：最后一趟没有进行冒泡排序的结束条件为：最后一趟没有进行“交换交换”。冒泡排。冒泡排序是一种稳定的排序算法。序是一种稳定的排序算法。时间分析时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡一趟起泡“比较比较”的次数：的次数：“移动移动”的次数：的次数：n-10 最坏的情况（关键字在记录序列中逆序有序）：需进行最坏的情况（关键字在记录序列中逆序有序）：需进行 n-1n-1趟起泡趟起泡“比较比较”的次数：的次数：“移动移动”的次数：的次数：希尔排序希尔排序基本

17、思想：对待排记录序列先作基本思想：对待排记录序列先作“宏观宏观”调整，再作调整，再作“微微观观”调整。所谓调整。所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插的插入排序。即：将记录序列分成若干子序列，每个子序列分入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序别进行插入排序,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时，时，再对全体记录进行一次直接插入排序。假设将再对全体记录进行一次直接插入排序。假设将n n个记录分个记录分成成d d个子序列，则这个子序列，则这d d个子序列分别为：个子序列分别为：R1 R1，R1+dR1+d，R1+2dR1+2

18、d，R1+kd R1+kd R2 R2，R2+dR2+d，R2+2dR2+2d，R2+kd R2+kd Rd Rd，R2dR2d，R3dR3d，RkdRkd，R(k+1)d R(k+1)d 其中，其中，d d称为增量，它的值在排序过程中从大到小逐渐缩称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为小，直至最后一趟排序减为1 1。例如：例如：第二趟希尔排序，设增量d=3 第三趟希尔排序，设增量d=1希尔排序的算法描述如下希尔排序的算法描述如下:Procedure ShellInsert(r:List;d:Integer);本算法对直接插入算法作了以下本算法对直接插入算法作了以下

19、 修改：修改：1.1.前后记录位置的增量是前后记录位置的增量是d d，而不是，而不是1 1；2.r02.r0只是暂存单元只是暂存单元,不是哨兵。当不是哨兵。当j=0j=0时时,插入位置已找到。插入位置已找到。Begin For i:=d+1 to n Do If(ri.key0)and(r0.key rj.key)Do rj+d=rj;记录后移，查找插入位置记录后移，查找插入位置 j:=j-d;rj+d=r0;插入插入 End;Procedure Shell_sort(r:List,dlta:Array of Integer;t:Integer);Begin 按增量序列按增量序列dlta0.t

20、-1dlta0.t-1对顺序表对顺序表L L作希尔排序。作希尔排序。For k=0 to t Do ShellInsert(r,dltak);End;先取定一个两项之间的距离先取定一个两项之间的距离d d1 1(n,(n,其中其中n n为整个表的长度为整个表的长度),),反复比较每两个相距反复比较每两个相距d d1 1的项的项,直到以直到以d d1 1为距离划分的组排序好为止为距离划分的组排序好为止(至此一趟排序完成至此一趟排序完成),),然后取然后取d d2 2dd1 1,再继续以再继续以d d2 2为距离反复比较每为距离反复比较每两个相距为两个相距为d d2 2的项的项,依此类推依此类推.

21、取每个取每个d di+1i+1 d1 Do d:=d div2;Repeat all:=True;For i:=1 to n-d do j:=i+d;if rirj then max:=ri;ri:=rj;rj:=max;all:=false;Until all For i:=1 to n Do Write(ri);End;选择排序选择排序基本思想：首先在基本思想：首先在n n个记录中选择一个具有最小或最大个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在录交换位置。然后在r2r2至至rnrn中选择一

22、个最小或最大中选择一个最小或最大的值与的值与r2r2交换位置，交换位置，依此类推，直至，依此类推，直至rn-1rn-1和和rnrn比较完毕。比较完毕。Procedure Select_sort(var r:List;n:Integer);Begin For i:=1 to n-1 Do m:=i;For j:=i+1 to n Do If rj.keyrm.key then m:=j;If m i then x:=ri;ri:=rm;rm:=x;End;算法的复杂性分析：算法的复杂性分析：当选则第一个最小值时需进行当选则第一个最小值时需进行n-1n-1次比较，选第二个最小值时需次比较，选第二个

23、最小值时需进行进行n-2n-2次比较，次比较，选，选n-1n-1个最小值时需进行个最小值时需进行n-(n-1)n-(n-1)次比较，次比较，所以总的比较次数为所以总的比较次数为(n-1)+(n-2)+(n-1)+(n-2)+2+1=n(n-1)/2+2+1=n(n-1)/2故排序故排序n n个记录需要时间为个记录需要时间为O(nO(n2 2)。由于执行一次交换，需三次移动记录，最多交换由于执行一次交换，需三次移动记录，最多交换n-1次，故最多移次，故最多移动次数为动次数为3(n-1)堆排序堆排序堆是满足下列性质的数列堆是满足下列性质的数列RR1 1,R,R2 2,，R Rn n：或或若将此数列

24、看成是一棵完全二叉树，则堆或是空树或是满足下若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于子树不空时，根结点的值小于(或大于或大于)左、右子树根结点的值。左、右子树根结点的值。9683273811 09下列两个序列为堆，对应的完全二叉树如下图下列两个序列为堆，对应的完全二叉树如下图96，83，27，38，11，09 12，36，24，85，47，30，53，911236248547305391建堆的过程：建堆的过程：1.首先将一个关键字集合用完全二叉树的

25、形式排列首先将一个关键字集合用完全二叉树的形式排列;如给定关键字集合为如给定关键字集合为46,55,13,42,94,17,05,70组成的完全二叉组成的完全二叉 树如下：树如下：4655134294 1705702.开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法 的思想是这样的：假设集合的思想是这样的：假设集合r有有m个结点，从某个结点个结点，从某个结点i(第一次第一次 i=m/2)开始筛选，先看第开始筛选，先看第i个结点的左右子树，设第个结点的左右子树，设第i个结点的个结点的 左子树为左子树为k j，右子树为，右子树为kj+1，

26、若若k j kj则对调，小的上来大的下去。然后则对调，小的上来大的下去。然后kj作作 为新的根结点，在对新的根结点的左右子树进行判断，重复上为新的根结点，在对新的根结点的左右子树进行判断，重复上 述过程，直到某个结点的左或右子树根结点的下标大于述过程，直到某个结点的左或右子树根结点的下标大于m为止。为止。第一次调用筛选法：第一次调用筛选法：m=8,i=m/2=4,从从i=4开始，看开始，看k 4的左右子树，仅有左子树，的左右子树，仅有左子树，因此因此42与与70比较，比较，4270，所，所以不变。以不变。j=i*2=8,i=j，再向下，再向下看，此时的看，此时的i无左右子树无左右子树,所以所以

27、返回，如右图所示。返回，如右图所示。4655134294 17057046,55,13,42,94,17,05,70第二次调用筛选法：第二次调用筛选法：i=3,k 3=13,13的左右子树为的左右子树为17和和05，因因1705,进行对调，此时进行对调，此时13无无左右子树，所以返回。左右子树，所以返回。4655054294 17137046,55,05,42,94,17,13,70第三次调用筛选法：第三次调用筛选法：i=2,k 2=55,因为因为4294，所以沿左子树筛选，所以沿左子树筛选，4255,进行对调，此时进行对调，此时55还有左还有左子树子树70，因，因5570，所以不变，所以不变

28、，再向下再向下70无左右子树，所以返无左右子树，所以返回，此时二叉树如右图所示。回，此时二叉树如右图所示。4642055594 17137046,42,05,55,94,17,13,70第四次调用筛选法：第四次调用筛选法：i=1,k 1=46,因为因为0542，所以沿右子树筛选，所以沿右子树筛选，0546,进行对调，此时进行对调，此时46还有左还有左右子树右子树17,13，因，因1317，所以再，所以再沿右子树筛选，沿右子树筛选，13rj+1 (j=2*i),则沿右分支筛选，否则沿左分支筛选则沿右分支筛选，否则沿左分支筛选Begin i:=k;j:=2*i;x:=ri;while j=m Do

29、 If(jrj+1.key)then j:=j+1;沿右筛沿右筛 If x.keyrj.key then ri:=rj,i:=j;j:=2*i;关键字对调，在准备与下一层比较关键字对调，在准备与下一层比较 else j:=m+1;强制跳出强制跳出while循环循环|ri:=x;将将x放到适当的位置上放到适当的位置上End;堆排序的过程：堆排序的过程：用拔尖的方法将对顶输出，把最后一个元素送到用拔尖的方法将对顶输出，把最后一个元素送到树根上，然后从树根上，然后从i=1开始，调用筛选算法重新建堆，再将堆顶输出开始，调用筛选算法重新建堆，再将堆顶输出将最后一个送到树根，再重新建堆，如此反复，直到得到

30、最后全将最后一个送到树根，再重新建堆，如此反复，直到得到最后全部排序好的关键字序列。部排序好的关键字序列。算法描述如下：算法描述如下：Procedure Heap_sort(var r:List;n:Integer);Begin For k:=n div 2 DownTo 1 Do Call Sift(r,k,n);从第从第 n/2 开始进行筛选建初始堆开始进行筛选建初始堆 For k:=n DownTo 2 Do t:=rk;rk:=r1;r1:=t;Write(rk);Call Sift(r,1,k-1);Write(r1);End;以上面建的堆为例以上面建的堆为例,说明重建堆的执行过程。

31、说明重建堆的执行过程。输出输出050570r10542135594 1746707042135594 1746051342175594 7046重建堆重建堆输出输出131346r14642175594 701305重建堆重建堆051742465594 701305输出输出171770r17042465594 171305重建堆重建堆4255467094 171305输出输出424294r19455467042 171305重建堆重建堆4655947042 171305输出输出464670r17055944642 171305重建堆重建堆5570944642 171305输出输出555594r1

32、9470554642 171305重建堆重建堆7094554642 171305输出输出707094r19470554642 171305退出退出K K循环循环打印打印94949470554642 171305堆排序的时间复杂度分析：堆排序的时间复杂度分析：1.1.对深度为对深度为k k的堆，的堆，“筛选筛选”所需进行的关键字比较的所需进行的关键字比较的次次 数至多为数至多为2(k-1);2(k-1);2.2.对对n n个关键字，建成深度为个关键字，建成深度为 的堆，所需进的堆，所需进行的关键字比较的次数至多为行的关键字比较的次数至多为4n;4n;3.3.调整调整“堆顶堆顶”n-1n-1次，总

33、共进行的关键字比较的次数次，总共进行的关键字比较的次数不超过不超过 因此，堆排序的时间复杂度为因此，堆排序的时间复杂度为O(nlogn)O(nlogn)共共n-2项相加项相加 快速排序快速排序快速排序又称分划交换排序，设输入文件有快速排序又称分划交换排序，设输入文件有n个记录个记录R1,R2,Rn,它们对应的关键字是它们对应的关键字是k1,k2,kn，该方法先，该方法先取文件中任一记录取文件中任一记录K(通常取第一个记录通常取第一个记录)，然后用，然后用K从两从两头到中间进行比较头到中间进行比较/交换，就能形成一个分划：凡是小于交换，就能形成一个分划：凡是小于等于等于K的被移到左边，凡是大于的

34、被移到左边，凡是大于K的被移到右边。的被移到右边。例例:初始关键字初始关键字46 55 13 42 94 05 17 70将将46 x第一次交换后第一次交换后 17 55 13 42 94 05 70ijji第二次交换后第二次交换后 17 13 42 94 05 55 70ji第三次交换后第三次交换后 17 05 13 42 94 55 70ji第四次交换后第四次交换后 17 05 13 42 46 94 55 70ji快速排序步骤：快速排序步骤：1.1.选定选定R R1 1为起点，且将为起点，且将R R1 1送送x x；2.2.从最末项从最末项R Rp p开始起指针开始起指针j j倒向前找到

35、第一个倒向前找到第一个k kj j x.keyx.key或或 i ji j时，则判时，则判ij?ix.keyx.key或或 ijij时，则判时，则判ij?i=x.key)and(ji)Do j:=j-1;If ij then ri:=rj;i:=i+1;while(ri.key=x.key)and(ij)Do i:=i+1;if ij then rj:=ri;j:=j-1;Until i=j;ri:=x;i:=i+1;j:=j-1;if lj then Quick_sort(r,l,j);if ip then Quick_sort(r,i,p);End;快速排序是目前内部排序中最快的方法。若关

36、键字的分布式均匀快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。令令T(n)为分类为分类n个记录所需之比较次数，则有：个记录所需之比较次数，则有：T(n)cn+2T(n/2)(其中其中cncn为进行一趟排序所需的时间为进行一趟排序所需的时间)T(n)cn+2(cn/2+2T(n/4)2cn+4T(n/4)log +nT(2)=O(nlog2 n)快速排序算法的性能分析：快速排序算法的性能分析：但如果原来的文件是有次序的，则每个分划操作几乎是无用的，但如果原来的文件是有次序

37、的，则每个分划操作几乎是无用的，因为它仅使文件的大小减少一个元素，所以这种情况使得快速因为它仅使文件的大小减少一个元素，所以这种情况使得快速排序根本不快，它的运行时间接近于冒泡排序，时间复杂性为排序根本不快，它的运行时间接近于冒泡排序，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。因此，快速排序偏爱一个无次序的文件。快速排序是一种不稳定的排序算法。快速排序是一种不稳定的排序算法。归并排序的基本思想是：将两个或两个以上的有序子归并排序的基本思想是：将两个或两个以上的有序子序列序列“归并归并”为一个有序序列。为一个有序序列。在内部排序中，通常采用的是在内部排序中，通常采用的是2-2-

38、路归并排序。即：将路归并排序。即：将两个位置相邻的有序子序列两个位置相邻的有序子序列 归并为一个有序序列。归并为一个有序序列。归并排序归并排序2-2-路归并排序算法路归并排序算法Procedure merge(l,m,n:Integer;r,r2:List);表表r可以看作是首尾相接的两个文件，将其合并到第三个表可以看作是首尾相接的两个文件，将其合并到第三个表r2上上 第一个文件的下标从到第一个文件的下标从到m，第二个文件的下标从，第二个文件的下标从m+1到到nBegin i:=l;k:=1;j:=m+1;while(i=m)and(j=n)Do if ri.keym then Copy(r,

39、j,n,r2)else Copy(r,i,m,r2);End;采用采用2-路归并算法进行排序的思想：先将初始文件分成长度为路归并算法进行排序的思想：先将初始文件分成长度为的的n个子文件并且合并到相邻的子文件。则可以得到大约个子文件并且合并到相邻的子文件。则可以得到大约n/2个长个长度为度为2的子文件，重复上述过程，直到仅剩下一个长度为的子文件，重复上述过程，直到仅剩下一个长度为n的文件。的文件。下面的例子显示了这个排序过程下面的例子显示了这个排序过程(直接合并排序直接合并排序),),每个子文件每个子文件用方括号括起来。用方括号括起来。初始文件初始文件 25 57 48 37 12 92 86

40、3325 57 48 37 12 92 86 33n=8n=8个子文件个子文件 25 57 48 37 12 92 86 3325 57 48 37 12 92 86 33第一趟第一趟 25 57 37 48 12 92 33 8625 57 37 48 12 92 33 86 第二趟第二趟 25 37 48 57 12 33 86 9225 37 48 57 12 33 86 92 第三趟第三趟 12 25 33 37 48 57 86 9212 25 33 37 48 57 86 92设一个辅助数组设一个辅助数组aux,aux,被用于保存合并被用于保存合并x x的两个子数组所得的结果。的两

41、个子数组所得的结果。变量变量sizesize用于控制被合并的子文件的大小。因为每次被合并的用于控制被合并的子文件的大小。因为每次被合并的两个子文件总是两个子文件总是x x的两个子数组的两个子数组,所以必须用变量来指出子数组所以必须用变量来指出子数组的上下界。的上下界。ib1ib1和和ub1ub1分别表示待合并的第一个子文件的下界与分别表示待合并的第一个子文件的下界与上界上界,ib2,ib2和和ub2ub2分别表示待合并的第二个子文件的下界和上界分别表示待合并的第二个子文件的下界和上界.变量变量i i和和j j用来指示待合并的两个子文件用来指示待合并的两个子文件(即源文件即源文件)的元素的元素,

42、变量变量k k用于指示合并得到的目标子文件的元素。用于指示合并得到的目标子文件的元素。归并排序算法：归并排序算法：Procedure Merge_sort(var x:List;n:Integer);Begin size:=1;while sizen Do ib1:=1;k:=1;while ib1+sizen then ub2:=n else ub2:=ib2+size-1;call Merge(ib1,ub1,ib2,x,aux);ib1:=ub2+1;i:=ib1;while k=n Do auxk:=xi;k:=k+1;i:=i+1;For k:=1 to n Do xk:=auxk;

43、size:=size*2;End;从上面的算法可以看出从上面的算法可以看出sizesize变量的取值不超过变量的取值不超过loglog2 2 n n个，对个，对sizesize的每一个取值都扫描的每一个取值都扫描n n个记录个记录,所以归并排序的时间复杂所以归并排序的时间复杂性为性为O(nlog2 n)Procedure Msort(r,r1:List;s,t:Integer);将将rs.t进行进行2-2-路归并排序为路归并排序为r1s.tBegin if(s=t)then r1s=rs else m=(s+t)/2;将将rs.t平分为平分为rs.m和和rm+1.t Msort(r,r2,s,

44、m);递归地将递归地将rs.m归并为有序的归并为有序的r2s.m Msort(r,r2,m+1,t);递归地递归地rm+1.t归并为有序的归并为有序的r2m+1.t Merge(r2,r1,s,m,t);将将r2s.m和和r2m+1.t归并到归并到r1s.t End;Procedure Merge_sort(r:List)Begin MSort(r,r1,1,n);对记录序列对记录序列r1.n作作2-2-路归并排序路归并排序 End;递归算法描述如下：递归算法描述如下：基数排序基数排序借助借助“多关键字排序多关键字排序”的思想来实现的思想来实现“单关键字排序单关键字排序”的算法。的算法。多关键

45、字的排序多关键字的排序假设有假设有n n个记录的序列个记录的序列 R R1 1,R,R2 2,，R Rn n，每个记录，每个记录R Ri i中含有中含有d d个个关键字关键字(K(Ki i0 0,K,Ki i1 1,K,Ki id-1d-1),),则称上述记录序列对关键字则称上述记录序列对关键字(K(Ki i0 0,K,Ki i1 1,K,Ki id-1d-1)有序是指：对于序列中任意两个记录有序是指：对于序列中任意两个记录RiRi和和Rj(1ijn)Rj(1ijn)都满足下列都满足下列(词典词典)有序关系：有序关系：(K(Ki i0 0,K,Ki i1 1,K,Ki id-1d-1)(K)(

46、Kj j0 0,K,Kj j1 1,K,Kj jd-1d-1)其中其中K K0 0被称为被称为“最主最主”位关键字，位关键字，K Kd-1d-1被称为被称为 “最次最次”位关键字。位关键字。实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:最高位优先最高位优先MSDMSD法法：先对：先对K K0 0进行排序，并按进行排序，并按K K0 0的不同值将记录序列的不同值将记录序列分成若干子序列之后，分别对分成若干子序列之后，分别对K K1 1进行排序，进行排序，依次类推，直，依次类推，直至最后对最次位关键字排序完成为止。至最后对最次位关键字排序完成为止。最低位优先最低位优先LSDLSD法

47、：法：先对先对K Kd-1d-1进行排序，然后对进行排序，然后对K Kd-2d-2进行排序，依进行排序，依次类推，直至对最主位关键字次类推，直至对最主位关键字K K0 0排序完成为止。排序过程中不排序完成为止。排序过程中不需要根据需要根据“前一个前一个”关键字的排序结果，将记录序列分割成若关键字的排序结果，将记录序列分割成若干个干个(“前一个前一个”关键字不同的关键字不同的)子序列。子序列。例如例如:学生记录含三个关键字学生记录含三个关键字:系别、班号和班内的序列系别、班号和班内的序列号，其中以系别为最主位关键字。号，其中以系别为最主位关键字。LSDLSD的排序过程如下的排序过程如下:无序序列

48、无序序列3,2,301,2,153,1,202,3,182,1,20对对K2排序排序1,2,152,3,183,1,202,1,203,2,30对对K1排序排序3,1,202,1,201,2,153,2,302,3,18对对K0排序排序1,2,152,1,202,3,183,1,203,2,30链式基数排序链式基数排序 假如多关键字的记录序列中，每个关键字的取值范围相假如多关键字的记录序列中，每个关键字的取值范围相同，则按同，则按LSDLSD法进行排序时，可以采用法进行排序时，可以采用“分配分配-收集收集”的方法，的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的其好处是不需要进行

49、关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种，此时可以采用这种“分配分配-收集收集”的办法进行排序，称作基的办法进行排序，称作基数排序法。数排序法。例如：对下列这组关键字例如：对下列这组关键字 209,386,768,185,247,606,230,834,539 209,386,768,185,247,606,230,834,539 首先按其首先按其“个位数个位数”取值分别为取值分别为0,1,0,1,，9 9“分配分配”成成1010组组，之后按从，之后按从0 0至至9 9的顺

50、序将它们的顺序将它们“收集收集”在一起在一起;然后按其然后按其“十位十位数数”取值分别为取值分别为0,1,0,1,，9 9“分配分配”成成1010组，之后再按从组，之后再按从0 0至至9 9的顺序将它们的顺序将它们“收集收集”在一起在一起;最后按其最后按其“百位数百位数”重复一遍上重复一遍上述操作，便可得到这组关键字的有序序列。述操作，便可得到这组关键字的有序序列。在计算机上实现基数排序时，为减少所需辅助存储空间，应在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：采用链表作存储结构，即链式基数排序，具体作法为：1.1.待排序记录以指针相链，构