算法ppt课件第9章(内排序).ppt

《算法ppt课件第9章(内排序).ppt》由会员分享，可在线阅读，更多相关《算法ppt课件第9章(内排序).ppt（74页珍藏版）》请在三一办公上搜索。

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) ,这样一种运算称为排序。,9.1 基本概念,如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。,排序：,排序的稳定性：,即，1)

2、 K(i) K (i+1) (1 i n-1) 2)若在输入文件中ij,且Ki =K j ,则在经过排序后 的文件中仍Ri先于Rj,排序,内排序：整个排序过程都在内存进行的排序。,外排序：当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问。,例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,内部排序的方法 在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,使有序

3、区中记录的数目增加一个或几个的操作称为一趟排序。,存放待排序数据的数据结构：typedef struct int key; datatype otheritem; /其他域 records;typedef struct records Listn+1;,逐步扩大记录有序序列长度的方法大致有下列几类：,1.插入类 :将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；,2.交换类 :通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；,3.选择类 :从记录的无序子序列中“选择”关键字最小或最

4、大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度；,4.归并类 :通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度；,5.其它方法。,内 排 序,插入类排序,直接插入排序,折半插入排序,希尔排序,交换类排序,冒泡排序,快速排序,选择类排序,选择排序,堆排序,归并类排序,归并排序,其他排序,计数排序,基数排序,9.2 计数排序,对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值，从而找到该记录的正确排序位置。,key info count,设一个记录有三个域：,排序算法的思想：,for(i=1;in;i+) for(j=i+1;j=n;j

5、+) if (Ri.key)Rj.key) Ri.count= Ri.count+1; else Rj.count=Rj.count+1;,void countsort(List R, int n) for(i=1;i=n;i+) Ri.count=1; /对所有元素的count域置1；,算法如下：,设文件有n个记录，则外循环：i=1时，内循环要做n-1次比较；i=2时，内循环要做n-2次比较；i=n-1时，内循环要做1次比较；总的比较次数为(n-1)+(n-2)+1=n(n-1)/2,算法性能分析：,所以，算法所需时间为O(n2)，由于不需要记录移动和额外空间，同时算法简单，当n较小时，可采

6、用本算法。,例 关键字序列46，55，13，42，44，17，05，70,9.3 直接插入排序,假设在排序过程中，记录序列R1.n的状态为： 则一趟插入排序的基本思想为：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。,显然，完成这个“插入”需分三步进行：,1查找Ri的插入位置j+1；,2将Rj+1.i-1中的记录后移一个位置；,3将Ri复制到Rj+1的位置上。,直接插入排序：利用顺序查找实现“在R1.i-1中查找Ri的插入位置”的插入排序。,注意直接插入排序算法的三个要点：,1. 从Ri-1起向前进行顺序查找，监视哨设置在R0； R0= Ri； 设置“哨

7、兵” j=i-1; while(R0.keyRj.key) j=j-1; / 从后往前找 Return(j+1); 返回Ri的插入位置为j+1,2. 对于在查找过程中找到的那些关键字不小于Ri.key的记 录，并在查找的同时实现记录向后移动； while(R0.keyRj.key) Rj+1=Rj; j=j-1;,3. i = 2，3，, n, 实现整个序列的排序。,排序算法如下：void insort(List r, int n)/r为给定的表，其记录为ri，i=0，1，n，x为暂存单元。 for (i=2; i=n; i+) r0=ri; /r0作为标志位 j=i-1; while (r0

8、.keyrj.key) rj+1=rj; j-; /j从i-1至0，rj.key与ri.key进行比较 rj+1=r0; /insort,排序的时间分析：实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：,最坏的情况（关键字在记录序列中逆序有序）：,总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。,9.4 折半插入排序,排序算法的思想：由于直接插入排序的内循环(从1到i-1)的查找(或说是比较)是在(部分)有序表的环境下进行的，所

9、以内循环用“折半查找法”，比用顺序查找法快。,算法描述如下：void binsort(List r, int n) for(i=2;i=n;i+) r0=ri;low=1; high=i-1; while(low=high) m=(low+high)/2; if r0.keyrm.key high=m-1; else low=m+1; for (j=i-1;j=low;j-) rj+1=rj;/把从第low起到第i-1各记录后移 rlow=r0;/将第i个记录插入 /binsort,9.5 冒泡排序,排序算法的思想：比较k1和k2, 如果这些关键字的值不符合排序顺序, 就交换k1和k2；然后对

10、记录k2和k3, k3和k4等等进行相同的工作。直到kn-1和kn为止, 到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录, 使得所有记录最终被排好序。,例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1k2kn (n=5)。,因为到第四趟就没有交换的偶对了,所以整个排序结束。,算法描述如下:void bubblesort(List r,int n) for (m=1;mri) max=rm; rm=ri; ri=max; all=F; k-; while(all=F)&(k!=1),冒泡排序

11、的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种稳定的排序算法。,时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡,最坏的情况（关键字在记录序列中逆序有序）：需进行 n-1趟起泡,9.6 希尔排序,基本思想：对待排序记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。,假设将n个记录分成d个子序列，则这d个子序列分别为： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd

12、，R2d，R3d，Rkd，R(k+1)d 其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。,例如：,第二趟希尔排序，设增量d = 3,第三趟希尔排序，设增量d = 1,希尔排序的算法描述如下:void ShellInsert (List r,int d) /本算法对直接插入算法作了以下修改：/ 1. 前后记录位置的增量是d，而不是1；/ 2. r0只是暂存单元，不是哨兵。当j0) and (r0 rj) rj+d = rj; /记录后移，查找插入位置 j=j-d; rj+d = r0;/插入 ,for (i=2;i= n ; i+) r0=ri; j=i-1; w

13、hile ( r0.keyrj.key) rj+1=rj; j=j-1; rj+1=r0; ,Void Shell_sort (List r, int dlta, int t); /按增量序列dlta0.t-1对顺序表r作希尔排序 for(k=0;k=t;k+) ShellInsert(r, dltak); ,先取定一个两项之间的距离d1(n,其中n为整个表的长度),反复比较每两个相距d1的项,直到以d1为距离划分的组排序好为止(至此一趟排序完成); 然后取d2d1,再继续以d2为距离反复比较每两个相距为d2的项,依此类推.取每个di+1 di,直到dt=1为止。,第二趟后结果,d2=2,05

14、 17 13 42 46 55 94 70,13,46分别交换两次,05 13 17 42 46 55 70 94,第三趟后结果,d3=1,North China Electric Power University,9.7 选择排序,基本思想：首先在n个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在r2至rn中选择一个最小或最大的值与r2交换位置，依此类推，直至rn-1和rn比较完毕。,void slsort(List r,int n)/每次从rj(j=i+1,n)中选了最小值，与ri(i=1,2,n-1)交换，进行分类 for (i=1;i=n

15、-1;i+) /共进行n-1趟排序 m=i; for (j=i+1;j=n;j+) if (rj.keyrm.key) m=j; /m指示关键字最小的记录的序号 if (m!=i) x=ri; ri=rm; rm=x; ,例 关键字序列055，55，60，13，05，94，17，70,利用选择排序算法进行排序。,不稳定,算法的复杂性分析：当选则第一个最小值时需进行n-1次比较，选第二个最小值时需进行n-2次比较，选n-1个最小值时需进行n-(n-1)次比较，所以总的比较次数为(n-1)+(n-2)+2+1=n(n-1)/2故排序n个记录需要时间为O(n2)。,由于执行一次交换，需三次移动记录，

16、最多交换n-1次，故最多移动次数为3(n-1),North China Electric Power University,9.8 堆排序,1.定义：堆是由n个记录的线性序列R1, R2, ，Rn; 其关键字序列k1,k2, ，kn,满足下列特性时，称之为堆。,或,若将此数列看成是一棵完全二叉树的顺序存储表示，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。,下列两个序列为堆，对应的完全二叉树如下图96，83，27，38，11，09,kik2i,kik2i+1,kik2i,kik2i+1,大根堆,小根堆,12

17、，36，24，85，47，30，53，91,1) 首先将一个关键字集合用完全二叉树的形式排列; 如给定关键字集合为46,55,13,42,94,17,05,70组成的完全二叉树如下：,2. 建堆的过程：,2)开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法的思想是这样的： 假设集合r有m个结点，从某个结点i（第一次 i=m/2 ）开始筛选;, 先看第i个结点的左右子树，设第i个结点的左子树为kj ,右子树为kj+1。若kj kj则对调，小的上来大的下去。, 然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。,第一次调用

18、筛选法：m=8,i=m/2=4,从i=4开始，看k4的左右子树，仅有左子树，因此42与70比较，4270，所以不变。j=i*2=8，i=j，再向下看，此时的i无左右子树,所以返回，如右图所示。,第二次调用筛选法：i=3, k3 =13,13的左右子树为17和05，因1705,故沿右子树比较，1305,进行对调，此时13无左右子树，所以返回。,North China Electric Power University,05,13,46, 55, 13, 42, 94, 17, 05, 70,46, 55, 05, 42, 94, 17, 13, 70, 先看第i个结点的左右子树，设第i个结点的左

19、子树为kj ,右子树为kj+1。若kj kj则对调，小的上来大的下去。 然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。,第三次调用筛选法：i=2, k2=55,因为4294，所以沿左子树筛选，4255,进行对调，此时55还有左子树70，因5570，所以不变，再向下70无左右子树，所以返回，此时二叉树如右图所示。,第四次调用筛选法：i=1, k1=46,因为0542，所以沿右子树筛选，0546,进行对调，此时46还有左右子树17,13，因1317，所以再沿右子树筛选，1346,所以对调，46无左右子树，所以返回，此时二叉树

20、如右图所示。,North China Electric Power University,55,42,46,05,46,13,46, 42, 05, 55, 94, 17, 13, 70,05, 42, 13, 55, 94, 17, 46, 70, 先看第i个结点的左右子树，设第i个结点的左子树为kj ,右子树为kj+1。若kj kj则对调，小的上来大的下去。 然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。,3. 建堆的算法void sift(List r, int k, int m)/对m个结点的集合r从某个结点i=

21、k开始筛选，如果rjrj+1(j=2i)，则沿右/分支筛，否则沿左分支筛。把关键字大的筛到堆底。 i=k; j=2*i; x=ri; ri=x;/将x放在适当的位置/sift,North China Electric Power University,while (jrj+1.key) /左子树右子树 j+; /沿右筛 ,if (x.keyrj.key) ri=rj; i=j; j=2*i; /将关键字小的换到i位置，x.key再准备与下一层的比较,else j=m+1; /强制跳出while循环,以上面建的堆为例,说明重建堆的执行过程。,05,42,13,55,94,17,46,70,70,

22、42,13,55,94,17,46,05,13,42,17,55,94,70,46,46,42,17,55,94,70,05,05,05,70,X,05,42,13,55,94,17, 46,70,13,42,17,55,94,70, 46,05,13,46,13,70,4.堆排序过程,13,17,42,46,55,94,70,05,13,70,42,46,55,94,05,17,13,42,55,46,70,94,05,17,13,94,55,46,70,05,17,42,46,55,94,70, 13,05,X,17,70,17,42,55,46,70,94,17, 13,05,42,94

23、,42,70,42,17,13,46,55,94,70,05,42,17,13,70,55,94,05,46,42,17,13,55,70,94,05,46,42,17,13,94,70,05,46,55,94,70,42,17, 13,05,46,70,46,X,55,70,94,46,42,17, 13,05,55,94,55,70,70,70,94,55,46,42,17,13,05,94,55,46,42,17,13,05,70,94,55,46,42,17, 13,05,70,94,70,94,70,55,46,42,17, 13,05,堆排序的过程：用拔尖的方法将堆顶输出,把最后一

24、个元素送到树根上,然后从i=1开始,调用筛选算法重新建堆,再将堆顶输出将最后一个送到树根,再重新建堆。如此反复,直到得到最后全部排序好的关键字序列。,算法描述如下：void heapsort (List r, int n) /对n个结点的集合r进行堆排序 for (i=n/2; i=1; i-) sift (r, i, n); /从第n/2个结点开始进行筛选建初始堆/headsort,for (k=n; k=2; k-) t=rk; rk=r1; r1=t; printf(“%d”,rk); sift(r,1,k-1); /重建堆,rintf(“%d”,r1); /输出最后一个元素即最大元素,

25、North China Electric Power University,1）对深度为h的堆，“筛选”所需进行的关键字比较的次 数至多为2(h-1);,5.堆排序的时间复杂度分析,因此，堆排序的时间复杂度为O(nlogn),3）调整“堆顶”n-1次，总共进行的关键字比较的次数不 超过：,例：关键字序列3，27，36，027 ,输出序列为：3，027，27，36,不稳定,6.堆排序的稳定性分析,North China Electric Power University,9.9 快速排序,快速排序又称分划交换排序，设输入文件有n个记录R1 , R2 , Rn ,它们对应的关键字是k1 ,k2 ,

26、 kn 。该方法先取序列中任一关键字K(通常取第一个)，然后用K从两头到中间进行比较/交换，就能形成一个分划：凡是小于等于K的被移到左边，凡是大于K的被移到右边。,1.快速排序的定义,North China Electric Power University,2. 快速排序步骤,2) 从最末项kn开始起指针j倒向前找到第一个kj x.key或 i j时，则判ij? 是，kj送ki ，i=i+1；,1) 选定k1为起点，且将k1送x；,3) 从ki项起指针i向前扫描，找到第一个ki x.key或 ij时，则判ij?是，ki送kj ， j=j-1；,4) 上述过程进行到i=j时停止，将x送ki ，

27、同时i=i+1； j=j-1,即x在正确位置上,并分K为K1和K2两个子集合；,5) 重复调用上述过程，直到将整个集合排序好为止。,例: 初始关键字46 55 13 42 94 05 17 70将46 x,第一次交换后 55 13 42 94 05 17 70 ,第二次交换后 17 55 13 42 94 05 70 ,第三次交换后 17 13 42 94 05 55 70 ,第四次交换后 17 05 13 42 94 55 70 ,至此，完成第一趟排序,17,55,05,94,46,第五趟排序后 05 13 17 42 46 55 70 94,第一趟排序后 17 05 13 42 46 94

28、 55 70 ,第二趟排序后 13 05 17 42 46 94 55 70 ,第三趟排序后 05 13 17 42 46 94 55 70 ,第四趟排序后 05 13 17 42 46 70 55 94,例: 初始关键字 46 55 13 42 94 05 17 70 ,接上例,void qksort (List r, int L, int P)/将rL至rP进行排序/qksort,3. 快速排序算法,do while (rj.key=x.key),i=L; j=P; x=ri; /置初值,ri=x; i+; j-; /一趟快排结束，将x移至正确位置 if (Lj) qksort(r,L,j

29、); /反复排序前一部分 if (iP) qksort(r,i,P); /反复排序后一部分,North China Electric Power University,快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。,4. 快速排序算法的性能分析,但如果原来的文件是有次序的，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。,令T(n)为分类n个记录所需之比较次数, 设n=2k，则k=log2n，有： T(n) cn+2T(n/2) (其中cn为进行一趟排序所需的时间) T(n) cn+2(cn/2+2T(n/4) 2

30、cn+4T(n/4) kcn+2kT(1) =O(nlog2 n),5. 快速排序算法的稳定性分析,例：关键字序列5，2，02 ,第一次交换后 02 2 02 ,5x,第二次交换后 02 2 02,至此，完成排序，序列为 02, 2, 5,第一次交换 02 2 5,02x,第一趟,无交换 2 5,第二趟,5,不稳定,02,例 K=46,79,56,38,40,84（1）它的初始堆是： （2）快速排序第一趟结果：,（1）,（2）40，38，46，56，79，84,North China Electric Power University,归并排序的基本思想是：将两个或两个以上的有序子序列“归并”

31、为一个有序序列。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 归并为一个有序序列。,9.10 归并排序,North China Electric Power University,2-路归并排序算法,void merge(int L,int m,int n,List r,List r2)/表r可看成两个文件首尾相接的两个文件，即需合并的两个文件为r，合并到第三个表r2上 i=L; k=L;j=m+1; /从L开始 while (im) COPY(r,j,n,r2);/将rj至rn照抄至r2上，即表1完照抄第2个表 else COPY(r,i,m,r2) ;/将ri

32、至rm照抄至r2上/merge,North China Electric Power University,采用2-路归并算法进行排序的思想：先将初始文件分成长度为的n个子文件并且合并到相邻的子文件。则可以得到大约n/2个长度为2的子文件，重复上述过程，直到仅剩下一个长度为n的文件。,下面的例子显示了这个排序过程(直接合并排序),每个子文件用方括号括起来。,初始文件 25 57 48 37 12 92 86 33,n=8个子文件 25 57 48 37 12 92 86 33,第一趟 25 57 37 48 12 92 33 86,第二趟 25 37 48 57 12 33 86 92,第三趟

33、 12 25 33 37 48 57 86 92,North China Electric Power University,设一个辅助数组aux,被用于保存合并x的两个子数组所得的结果。变量size用于控制被合并的子文件的大小。因为每次被合并的两个子文件总是x的两个子数组,所以必须用变量来指出子数组的上下界。ib1和ub1分别表示待合并的第一个子文件的下界与上界,ib2和ub2分别表示待合并的第二个子文件的下界和上界.变量i和j用来指示待合并的两个子文件(即源文件)的元素,变量k用于指示合并得到的目标子文件的元素。,归并排序算法：,void mergsort(List x,int n)/x数

34、组用来存放待合并的文件，n为待合并子文件的个数 size=1;/置被合并的文件长度为1; while (sizen) ib1=1;/为第一个文件初始化下界 k=1;/k是辅助数组的标号,North China Electric Power University,while (ib1+sizen) ub2=n; else ub2=ib2+size-1; merge(ib1,ub1,ub2,x,aux); ib1=ub2+1; /复制最后一个文件 i=ib1; while (k=n) auxx=xi; k+; i+; ,/调整x和问题规模 for (k=1;k=n;k+) xk=auxk; siz

35、e=2*size;/while sizen do/mergsort,从上面的算法可以看出size变量的取值不超过log2n个，对size的每一个取值都扫描n个记录,所以归并排序的时间复杂性为O(nlog2n),North China Electric Power University,9.11 基数排序,借助“多关键字排序”的思想来实现“单关键字排序”的算法。1.多关键字的排序 假设有n个记录的序列 R1,R2,Rn,每个记录Ri中含有d个关键字(Ki0, Ki1,Kid-1),则称上述记录序列对关键字(Ki0, Ki1, ,Kid-1)有序是指:对于序列中任意两个记录Ri和Rj(1ijn)都

36、满足下列(词典)有序关系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为 “最次”位关键字。,实现多关键字排序通常有两种作法:最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序,，依次类推,直至最后对最次位关键字排序完成为止。,1.多关键字的排序,North China Electric Power University,最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字

37、的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。,例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:,North China Electric Power University,2. 链式基数排序 假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时,可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。,例如：对下列这组关键字 209, 386, 768

38、, 185, 247, 606, 230, 834, 539 首先按其“个位数”取值分别为0, 1, ，9, “分配”成10组之后按从0至9的顺序将它们“收集”在一起;然后按其“十位数” 取值分别为0, 1, ，9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。,2.链式基数排序,4)对每个关键字位均重复2)和3)两步。,在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：,待排序记录以指针相链，构成一个链表；,2)“分配”时，按当前“关键字位”所取值，将记录分配到不

39、同的“链队列”中，每个队列中记录的“关键字位”相同；,3)“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;,3.基数排序步骤,例如,有一组关键字179,208,306,093,859,984,055,009,271,033这些关键字是10进制数,基数rd=10,位数d=3.文件的初始状态是一个单链表,表头指针指向第一个记录:,第一趟分配对最低位关键字(个位数)进行,改变记录的指针值将文件中的记录分配至10个队列(桶)中去,每个队列中的记录关键字的个位数均相等，如图(a)所示,其中fi和ei分别为第i个队列的头指针和尾指针;第一趟收集是改变所有非空队尾记录的指针域,令其指向下一

40、个非空队列的队头记录,重新将10个队列中的记录链成一个链表文件:,前沿指针,(a) 第一趟分配之后,(b) 第一趟收集后的链式,第二趟分配,第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的,其过程和个位数相同,如图(c)所示,至此,排序完毕。若想从大到小排序,分配的过程与上述相同,收集的过程是从第e9队列向第e0方向收集。,009,208,306,984,093,055,033,859,271,179,093,055,033,(e) 第三趟分配之后,208,179,271,009,306,984,859,提醒注意：“分配”和“收集”的实际操作仅为修改链表中的指 针和设置队列的头、

41、尾指针；为查找使用，该链表尚需应用算法Arrange将它调 整为有序表。,North China Electric Power University,基数排序的算法简单描述如下：,数据类型定义如下：#define MAX_NUM_OF_KEY 8 /关键字项数（位数）的最大值#define RADIX 10#define MAX_SPACE 10000typedef struct KeysType keysMAX_NUM_OF_KEY; /关键字 InfoType otheritems; /其他数据项 int next; SLCell; /静态链表的结点类型typedef struct SLC

42、ell rMAX_SPACE; /静态链表的可利用空间，r0为头结点 int keynum; /记录的当前关键字个数 int recnum; /静态链表的当前长度 SLList; /静态链表的类型typedef int ArrTypeRADIX; /指针数组类型,North China Electric Power University,void Distribute(SLCell /将p所指的结点插入第j个子表中 ,算法9.10.2：void Collect(SLCell /t指向最后一个非空子表中的最后一个结点 ,North China Electric Power University,

43、算法9.10.3：void RadixSort(SLList /第i趟收集 ,基数排序的性能分析： 对于n个记录(每个记录含有d个关键字，每个关键字的取值范围为Rd个值)进行链式基数排序的时间复杂度为O(d(n+rd)，其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd),整个排序需进行d趟分配和收集。所需辅助空间为2rd个队列指针，当然由于需用链表做存储结构，则相对于其它以顺序结构存储记录的排序方法而言，还增加了n个指针域的空间。,North China Electric Power University,North China Electric Power Univer

44、sity,各种排序方法的综合比较一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序； 时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序； 时间复杂度为O(n)的排序方法只有基数排序。,2.当待排记录序列按关键字顺序有序时: 直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。,3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,North China Electric Power Unive

45、rsity,二、空间性能 :指的是排序过程中所需的辅助空间大小。1. 所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1)；2. 快速排序为O(logn )，为栈所需的辅助空间;3. 归并排序所需辅助空间最多，其空间复杂度为O(n );4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。,三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它 们在序列中的相对位置，在排序之前和经过排序之后，没 有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用 稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 选择排序，快速排序和堆排序是不稳定的排序方法。,各种排序方法的比较,North China Electric Power University,North China Electric Power University,Thank you for your listening,