数据结构第四讲.ppt

《数据结构第四讲.ppt》由会员分享，可在线阅读，更多相关《数据结构第四讲.ppt（88页珍藏版）》请在三一办公上搜索。

1、1,第四讲 查找和排序,2,本章出题特点,在历年统考里,大多以客观题的形式出现,具体如下:,3,一、查找,查找的基本概念顺序查找折半查找B树查找散列表,4,基本概念,在查找表上进行的基本操作有：查询，检索，插入和删除。若只是前两种操作的查找表则称为静态查找表，若兼有后面两种，则称为动态查找表。查找的基本操作是关键字间的比较，查找每一个元素所需比较次数的平均值称为平均查找长度，即,通常用平均查找长度来衡量查找算法的好坏。,5,例如,在关键字序列为3,9,1,5,8,10,6,7,2,4的线性表查找关键字为6的元素。顺序查找过程如下：,顺序查找,6,开始:3 9 1 5 8 10 6 7 2 4

2、第1次比较:3 9 1 5 8 10 6 7 2 4 i=0 第2次比较:3 9 1 5 8 10 6 7 2 4 i=1 第3次比较:3 9 1 5 8 10 6 7 2 4 i=2 第4次比较:3 9 1 5 8 10 6 7 2 4 i=3 第5次比较:3 9 1 5 8 10 6 7 2 4 i=4 第6次比较:3 9 1 5 8 10 6 7 2 4 i=5 第7次比较:3 9 1 5 8 10 6 7 2 4 i=6 查找成功,返回序号6,7,从顺序查找过程可以看到(不考虑越界比较in),ci取决于所查记录在表中的位置。如查找表中第1个记录R0时,仅需比较一次；而查找表中最后一个记

3、录Rn-1时,需比较n次,即ci=i。因此,成功时的顺序查找的平均查找长度为：,查找成功时的平均比较次数约为表长的一半。,思考题：不成功时的平均查找长度是多少？,8,二分查找 二分查找也称为折半查找，要求线性表中的结点必须己按关键字值的递增或递减顺序排列。思路：首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。,9,例如,在关键字有序序列2,4,7,9,10,14,18,26,32,40中采

4、用二分查找法查找关键字为7的元素。二分查找过程如下：,10,开始:2 4 7 9 10 14 18 26 32 40 low=0 high=9 mid=（0+9）/2=4 第1次比较:2 4 7 9 10 14 18 26 32 40 low=0 high=3 mid=（0+3）/2=1 第2次比较:2 4 7 9 10 14 18 26 32 40 low=2 high=3 mid=（2+3）/2=2第3次比较:2 4 7 9 10 14 18 26 32 40 R2.key=7 查找成功，返回序号2,11,二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的记录作为根；左子表和右子表

5、中的记录分别作为根的左子树和右子树。称为描述二分查找的判定树或比较树。,12,R0.10的二分查线的判定树(n=11),13,因此，在等概率假设下，二分查找成功时的平均查找长度为：,二分查找的适用场合：1、元素间必须有序；2、存储结构应当是顺序存储，而不宜适用链式结构。,14,索引查找（分块查找）,15,例如,设有一个线性表,其中包含25个记录,其关键字序列为：8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,4,88,96,87假设将25个记录分为5块,每块中有5个记录,该线性表的索引存储结构如下图所示。,16,若以二分

6、查找来确定块,则分块查找成功时的平均查找长度为：,若以顺序查找确定块,则分块查找成功时的平均查找长度为：,当s=时，ASL blk取极小值+1，即当采用顺序查找确定块时，应将各块中的记录数选定为。,17,B-树 B-树又称为多路平衡查找树,是一种组织和维护外存文件系统非常有效的数据结构。B-树中所有结点的孩子结点最大值称为B-树的阶,通常用m表示,从查找效率考虑,要求m3。一棵m阶B-树或者是一棵空树,或者是满足下列要求的m叉树：(1)树中每个结点至多有m个孩子结点(即至多有m-1个关键字)；(2)除根结点外,其他结点至少有m/2个孩子结点(即至少有m/2-1=(m-1)/2个关键字)；(3)

7、若根结点不是叶子结点,则根结点至少有两个孩子结点；,18,(4)每个结点的结构为：,其中,n为该结点中的关键字个数,除根结点外,其他所有结点的n大于等于m/2-1,且小于等于m-1；ki(1in)为该结点的关键字且满足kiki+1；pi(0in)为该结点的孩子结点指针且满足pi(0in-1)结点上的关键字大于等于ki且小于ki+1,pn结点上的关键字大于kn。(5)所有叶子结点都在同一层上,即B-树是所有结点的平衡因子均等于0的多路查找树。,19,一棵5阶B-树,20,B-树的查找 在B-树中查找给定关键字的方法类似于二叉排序树上的查找,不同的是在每个记录上确定向下查找的路径不一定是二路(即二

8、叉)的,而是n+1路的。因为记录内的关键字序列是有序的数量key1.n,故既可以用顺序查找,也可以用折半查找。在一棵B-树上顺序查找关键字为k的方法为：,21,将k与根结点中的keyi进行比较：(1)若k=keyi,则查找成功；(2)若kkey1,则沿着指针ptr0所指的子树继续查找；(3)若keyikkeyi+1,则沿着指针ptri所指的子树继续查找；(4)若kkeyn,则沿着指针ptrn所指的子树继续查找。,22,2.B-树的插入将关键字k插入到B-树的过程分两步完成：(1)利用前述的B-树的查找算法找出该关键字的插入结点(注意B-树的插入结点一定是叶子结点)。(2)判断该结点是否还有空位

9、置,即判断该结点是否满足nm-1,若该结点满足nm-1,说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上(即满足插入后结点上的关键字仍保持有序)；,23,若该结点有n=m-1,说明该结点已没有空位置,需要把结点分裂成两个。分裂的做法是,取一新结点,把原结点上的关键字和k按升序排序后,从中间位置(即m/2=(m+1)/2之处)把关键字(不包括中间位置的关键字)分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父亲结点中。如果父结点的关键字个数也超过Max,则要再分裂,再往上插,直至这个过程传到根结点为止。,24,例如 关

10、键字序列为：1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15。创建一棵5阶B-树。建立B-的过程如下图所示。,25,1 2 6 7,插入11,6,1 2,6,7 11,插入4,1 2 4,插入8,13,7 8 11 13,插入10,7 8 11 13,11 13,7 8,6 10,插入5,1 2 4 5,插入17,11 13 17,6 10 16,7 8 9,插入9,插入16,11 13 16 17,11 13,17 20,插入3,3 6 10 16,1 2,4 5,插入12,14,18,19,11 12 13 14,17 18 19 20,

11、插入15,14 15,11 12,13,13 16,3 6,10,插入20,16,3,10,1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15,26,27,3.B-树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的关键字个数m/2-1,将涉及到结点的“合并”问题。在B-树上删除关键字k的过程分两步完成：(1)利用前述的B-树的查找算法找出该关键字所在的结点。(2)在结点上删除关键字k分两种情况：一种是在叶子结点上删除关键字；另一种是在非叶子结点上删除关键字。,28,(3)在非叶子结点上删除关键字的过程：假设要删除关

12、键字keyi(1in),在删去该关键字后,以该结点ptri所指子树中的最小关键字keymin来代替被删关键字keyi所在的位置(注意ptri所指子树中的最小关键字keymin一定是在叶子结点上)。然后再以指针ptri所指结点为根结点查找并删除keymin(即再以ptri所指结点为B-树的根结点,以keymin为要删除的关键字,然后再次调用B-树上的删除算法)。这样也就把在非叶子结点上删除关键字k的问题转化成了在叶子结点上删除关键字keymin的问题。,29,(4)在B-树的叶子结点上删除关键字共有以下三种情况：假如被删结点的关键字个数大于Min,说明删去该关键字后该结点仍满足B-树的定义,则可

13、直接删去该关键字。假如被删结点的关键字个数等于Min,说明删去关键字后该结点将不满足B-树的定义。此时若该结点的左(或右)兄弟结点中关键字个数大于Min,则把该结点的左(或右)兄弟结点中最大(或最小)的关键字上移到双亲结点中,同时把双亲结点中大于(或小于)上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字k后该结点以及它的左(或右)兄弟结点都仍旧满足B-树的定义。,30,假如被删结点的关键字个数等于Min,并且该结点的左和右兄弟结点(如果存在的话)中关键字个数均等于Min。这时,需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。如果因此使双亲结

14、点中关键字个数小于Min,则对此双亲结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层。,31,10,14 15,13 16,3 6,1 2,7 8 9,17 18 19 20,4 5,11 12,7 9,删8,删16,17,13,13 17,18 19 20,删15,14,17,18,14 17,19 20,删4,5,1 2 3 5,6,6 10 13 18,13 18,对于前例生成的B-树，给出删除8，16，15，4等四个关键字的过程。,32,例如,对于上例生成的B-树,给出删除8,16,15,4等四个关键字的过程。,33,9.3.4 B+树 在索引文件组织中,经常使用B

15、-树的一些变形,其中B+树是一种应用广泛的变形。一棵m阶B+树满足下列条件：(1)每个分支结点至多有m棵子树。(2)除根结点外,其他每个分支结点至少有(m+1)/2棵子树。(3)根结点至少有两棵子树,至多有m棵子树。(4)有n棵子树的结点有n个关键字。,34,(5)所有叶子结点包含全部(数据文件中记录)关键字及指向相应记录的指针(或存放数据文件分块后每块的最大关键字及指向该块的指针),而且叶子结点按关键字大小顺序链接(可以把每个叶子结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直接指向数据文件中的记录)。(6)所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引的

16、索引块)中最大关键字及指向子结点的指针。,35,一棵4阶的B+树,36,m阶的B+树和m阶的B-树,定义中的前三点是相同的,主要的差异是：(1)在B+树中,具有n个关键字的结点含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n个关键字的结点含有(n+1)棵子树。(2)在B+树中,每个结点(除根结点外)中的关键字个数n的取值范围是m/2n m,根结点n的取值范围是1nm；而在B-树中,它们的取值范围分别是m/2-1n m-1和1nm-1。(3)B+树中的所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中,而在B-树中,叶子结点包含的关键字与其他结点包含的关键字是不

17、重复的。,37,(4)B+树中所有非叶子结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。而在B-树中,每个关键字对应一个记录的存储地址。(5)通常在B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点,所有叶子结点链接成一个不定长的线性链表。,38,哈希表查找哈希表的基本概念 哈希表(Hash Table)又称散列表,是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为n,设置一个长度为m(mn)的连续内存单元,以线性表中每个对象

18、的关键字ki(0in-1)为自变量,通过一个称为哈希函数的函数h(ki),把ki映射为内存单元的地址(或称下标)h(ki),并把该对象存储在这个内存单元中。h(ki)也称为哈希地址(又称散列地址)。把如此构造的线性表存储结构称为哈希表。,39,但是存在这样的问题,对于两个关键字ki和kj(ij),有kikj(ij),但h(ki)=h(kj)。把这种现象叫做哈希冲突。通常把这种具有不同关键字而具有相同哈希地址的对象称做“同义词”,由同义词引起的冲突称作同义词冲突。在哈希表存储结构的存储中,同义词冲突是很难避免的,除非关键字的变化区间小于等于哈希地址的变化区间,而这种情况当关键字取值不连续时是非常

19、浪费存储空间的。通常的实际情况是关键字的取值区间远大于哈希地址的变化区间。,40,归纳起来：(1)哈希函数是一个映象,即：将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可；(2)由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即：key1key2,而 f(key1)=f(key2)。(3)很难找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数,使冲突尽可能少地产生。,41,哈希函数构造方法 构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上,同时使计算过程尽可能简单以达到尽可能高的时间效

20、率。1.直接定址法 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。直接定址法的哈希函数h(k)为：h(k)=k+c 这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时,可用直接定址法的哈希函数；否则,若关键字分布不连续将造成内存单元的大量浪费。,42,2.除留余数法 除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=k mod p(mod为求余运算,pm)p最好取小于m的质数(素数)。,43,例 假设哈希表长度m=13,采用除留余数法哈希函数建立如下关键字集合的哈希表：16,

21、74,60,43,54,90,46,31,29,88,77。解：n=11,m=13,除留余数法的哈希函数为h(k)=k mod p,p应为小于等于m的素数,假设p取值13。则有：h(16)=3,h(74)=9,h(60)=8,h(43)=4,h(54)=2,h(90)=12,h(46)=7,h(31)=5,h(29)=3,h(88)=10,h(77)=12。注意：存在冲突。,44,3.数字分析法 该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。例如,对于一组关键字：92317602,92326875,92

22、739628,92343634,92706816,92774638,92381262,92394220 通过分析可知,每个关键字从左到右的第1、2、3位和第6位取值较集中,不宜作为哈希函数,剩余的第4、5、7和8位取值较分散,可根据实际需要取其中的若干位作为哈希地址。若取最后两位作为哈希地址,则哈希地址的集合为2,75,28,34,16,38,62,20。,45,哈希冲突解决方法,46,1.开放定址法 开放定址法是一类以发生冲突的哈希地址为自变量,通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法。(1)线性探查（测）法。线性探查法是从发生冲突的地址(设为d)开始,依次探查d的下一个地址(当

23、到达下标为m-1的哈希表表尾时,下一个探查的地址是表首地址0),直到找到一个空闲单元为止(当mn时一定能找到一个空闲单元)。线性探查法的数学递推描述公式为：d0=h(k)di=(di-1+1)mod m(1im-1),47,例 对上面构造的哈希表采用线性探查法解决冲突。解：h(16)=3,h(74)=9,h(60)=8,h(43)=4,h(54)=2,h(90)=12,h(46)=7,h(31)=5,h(29)=3 冲突 d0=3,d1=(3+1)mod 13=4 仍冲突 d2=(4+1)mod 13=5 仍冲突 d3=(5+1)mod 13=6 h(88)=10 h(77)=12 冲突 d0

24、=12,d1=(12+1)mod 13=0 建立的哈希表ha0.12如下表所示。,48,哈希表ha0.12,49,(2)平方探查法（二次探测法）。设发生冲突的地址为d,则平方探查法的探查序列为：d+12,d+22,。平方探查法的数学描述公式为：d0=h(k)di=(d0+i2)mod m(1im-1)平方探查法是一种较好的处理冲突的方法,可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元,但至少能探查到一半单元。,50,2.拉链法 拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。由于单链表中可插入任意多个

25、结点,所以此时装填因子根据同义词的多少既可以设定为大于1,也可以设定为小于或等于1,通常取=1。,51,例9.6 对上例构造的哈希表采用拉链法解决冲突。解：采用拉链法解决冲突建立的链表如下图所示。,52,9.4.4 哈希表上的查找 哈希表的主要目的是用于快速查找，且插入和删除操作都要用到查找。由于散列表的特殊组织形式，其查找有特殊的方法。设地址空间为HT0m-1，散列函数为H(key)，解决冲突的方法为R(x,i)，则在散列表上查找定值为K的记录的过程如图右图所示。,53,二、排序,基本概念插入排序交换排序选择排序归并排序基数排序,54,基本概念,注意：排序的对象是序列，而排序的依据是关键字。

26、只是我们为了方便，对序列中的每个元素只有关键字。若序列中有相同的关键字，排序后其相对位置没有改变，则该排序算法是稳定的，否则是不稳定的。,55,插入排序,思想是在一个已经有序的序列中插入元素，并保证插入后的有序性。直接插入排序（稳定）折半插入排序（稳定）折半插入排序在查找时节约了时间，但是移动的次序不变，所以时间复杂度依然不变。,56,例题：设待排序的表有10个记录,其关键字分别为3，10，7，8，20，5，8，2，1，6。给出采用希尔排序方法进行排序的过程（初始增量为5）。,初始状态：3，10，7，8，20，5，8，2，1，6,di=5的执行结果：3，8，2，1，6，5，10，7，8，20,

27、di=2的执行结果：2，1，3，5，6，7，8，8，10，20,di=1的执行结果：1，2，3，5，6，7，8，8，10，20,此处的关键字8是初始记录R3的还是初始记录R6的呢？,由此可知，希尔排序是稳定的还是不稳定的呢？,不稳定的,插入排序之希尔排序,57,交换排序,冒泡排序 一趟下来一个元素找到自己的正确位置快速排序,58,例10.3 设待排序的表有10个记录,其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法进行排序的过程。,59,快速排序 快速排序是由冒泡排序改进而得的。基本思想是：在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,

28、数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。,60,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序记录子序列(2),枢轴,一次划分,分别进行快速排序,61,s,t,low,high,设 Rs=52 为枢轴,将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字,将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key

29、 枢轴的关键字,high,23,low,80,high,14,low,52,例如,R0,52,low,high,high,high,low,62,可见，经过“一次划分”，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为:23,49,14,36,(52)58,61,97,80,75,在调整过程中，设立了两个指针：low 和high，它们的初值分别为：s 和 t。,之后逐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。,63,以后对所有的两部分分别重复上述过程,直至每部分内只有一个记录为止。简而言之,

30、每趟使表的第一个元素放入适当位置,将表一分为二,对子表按递归方式继续这种划分,直至划分的子表长为1。,64,例10.4 设待排序的表有10个记录,其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用快速排序方法进行排序的过程。,65,66,选择排序,直接选择排序堆排序,67,假设排序过程中，待排记录序列的状态为：,有序序列R0.i-1,无序序列 Ri.n,第 i 趟简单选择排序,从中选出关键字最小的记录,有序序列R0.i,无序序列 Ri+1.n,68,例10.5 设待排序的表有10个记录,其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用直接选择排序方法进行排序的过程。,

31、69,10.4.2 堆排序 堆排序是一树形选择排序,它的特点是,在排序过程中,将R1.n看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。堆的定义是：n个关键字序列K1,K2,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质)：(1)KiK2i 且 KiK2i+1 或(2)KiK2i 且 KiK2i+1(1in/2)满足第(1)种情况的堆称为小根堆,满足第(2)种情况的堆称为大根堆。下面讨论的堆是大根堆。,70,12,36,27,65,40,34,98,81,73,55,49,例如:,12,36,27,65,

32、40,14,98,81,73,55,49,是小根堆,不是堆,KEY:,KEY:,27,14,71,ri,r2i,r2i+1,若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,72,堆排序思想 对一组待排序的记录，按堆的定义建初始堆；将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值

33、的记录调整(排除)出无序区；重复上述步骤，直到全部记录排好序为止。结论：排序过程中，若采用小根堆，排序后输出的是非递减序 列；若采用大根堆，排序后输出的是非递增序列。,73,堆排序的关键 如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,74,堆排序的关键是构造堆,这里采用筛选算法建堆。所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。,堆,堆,筛选,75,40,55,49,49,40,比较,27,100,比较,比较,34,100,76,9,0,1,4,7,10,8,6,5,3,2,例如:设待排序的表有10个

34、记录,其关键字分别为9,0,1,4,5,3,2,10,8,6,7,它所对应的完全二叉树可表示如下:,7,5,10,4,10,3,1,10,9,构建初始堆的过程,初始堆,0,8,77,例10.6 设待排序的表有10个记录,其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。,78,堆排序过程：,79,80,归并排序 归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。,81,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列,归并为一个记录的有序序列。,有 序 序 列 Rl

35、.n,有序子序列 Rl.m,有序子序列 Rm+1.n,这个操作对顺序表而言，是轻而易举的。,82,例10.7 设待排序的表有8个记录,其关键字分别为18,2,20,34,12,32,6,16。说明采用归并排序方法进行排序的过程。,83,基数排序 前面所讨论的排序算法均是基于关键字之间的比较来实现的,而基数排序是通过“分配”和“收集”过程来实现排序,是一种借助于多关键字排序的思想对单关键字排序的方法。,84,以r为基数的最低位优先排序的过程是：假设线性表由结点序列a0,a1,an-l构成,每个结点aj的关键字由d元组(k,k,k,k)组成,其中0kr-1(0jn,0id-1)。在排序过程中,使用

36、r个队列Q0,Q1,Qr-1。排序过程如下：对i=0,1,d-1,依次做一次“分配”和“收集”(其实就是一次稳定的排序过程)。分配：开始时,把Q0,Q1,Qr-1各个队列置成空队列,然后依次考察线性表中的每一个结点aj(j=0,1,n-1),如果aj的关键字k=k,就把aj放进Qk队列中。收集：把Q0,Q1,Qr-1各个队列中的结点依次首尾相接,得到新的结点序列,从而组成新的线性表。,85,例如：,p369367167239237138230139,进行第一次分配,进行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367,167,237,367167237,138,368239139,369,239,139,138,86,进行第二次分配,p230237138239139,p230367167237138368239139,f3 r3,f6 r6,230,237,138,239,139,367,167,368,367167368,进行第二次收集,87,进行第三次收集之后便得到记录的有序序列,f1 r1,p230237138239139367167368,进行第三次分配,f2 r2,f3 r3,138,139,167,230,237,239,367,368,p138139167,230237239,367368,88,