fccjxxw.com
非常超级学习网 学习超级帮手
当前位置:首页 >> >>

最高位优先基数排序的一种实现方法


 1999 年 7 月

系统工程理论与实践

第 7 期 

最高位优先基数排序的一种实现方法
黄竞伟
( 武汉大学软件工程国家重点实验室, 湖北 武汉 430072)

摘要 给出了最高位优先基数排序算法的一种实现算法, 与其它的实现方法相比, 该方法易于扩展为 异步并行基数排序算法. 关键词 排序; 算法; 算法分析

A n I p lem en ta t ion M ethod of M SD R ad ix So rt m
HU AN G J ingw e i
(Sta te Key L ab. of Softw a re Eng ineering, W uhan U n iversity, W uhan 430072) Abstract  A n i p lem en ta tion m ethod of M SD rad ix so rt is p resen ted. Com p a red to m o ther i p lem en ta tion m ethod s of rad ix so rt, it is ea sy to be ex tended to a synch ronou s m p a ra llel rad ix so rt a lgo rithm. Keywords  so rting; a lgo rithm ; a lgo rithm s ana lysis

基数排序是一种常用的排序方法, 基数排序将关键字看作是以某个正整数 r 为基的数, 然后依次按关 键字的各个字位分别对记录进行排序. 通常有两种方法实现基数排序: 最高位优先 ( 简称 M SD 法) 和最低 位优先 ( 简称 L SD 法). L SD 法易于实现, 一般在数据结构教科书[1, 2 ] 中讨论较多. 若按 M SD 法必须将待 排序序列分割为若干子序列, 然后对各子序列再分别排序, 实现起来较为困难, 文献 [ 3 ] 推广了 L SD 链式基 数排序算法, 给出了 M SD 法的一种实现方法, 但该方法不易于扩展为并行算法. 在本文中, 我们给出了
M SD 法的一种实现方法, 该方法易于扩展为异步并行基数排序算法.

1  SD 法的一种实现方法 M
k i = (k 1 , k 2 , …, k d ) , 0 ≤ k ji ≤ r i i i
1

设有 n 个记录的序列{R 1 , R 2 , …, R n }, 每个记录 R i 的关键字 k i 是一个 d 位 r 进制数, 即设
1, 1 ≤ j ≤ d

其中关键字的第 1 位称为最高位, 第 d 位称为最低位, k i 称为最高位关键字, k id 称为最低位关键字, 按
M SD 法对序列{R 1 , R 2 , …, R n } 排序的思想是首先按最高位关键字对记录进行排序, 结果可以得到按最高

位关键字排好序的若干记录的子序列, 每一子序列中记录的最高位关键字相同, 第一个子序列中记录的最 高位关键字最小, 最后一个子序列中记录的最高位关键字最大, 再用同样的方式分别对这若干子序列中的 每一子序列中的记录按关键字 k 2 进行排序, 将其再分为若干子序列, 这时每一子序列中记录关键字 k 1 , k 2 i i i 都相同, 然后再用同样的方式分别对这若干子序列中的每一子序列中的记录按关键字位 k 3 进行排序, 这样 i 继续下去, 最后分别对每一子序列中的记录按关键字 k d 排序, 再将所有的子序列依次联接在一起就得到排 i 好序的序列. 例 用 M SD 法对下列关键字序列排序
{278, 109, 063, 064, 930, 589, 184, 505, 269, 008, 083}

α

α

收稿日期: 1998203217

? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

第7期

最高位优基数排序的一种实现方法

103

按最高位排序后, 原关键字序列分解为下列子序列
{063, 064, 008, 083}, {109, 184}, {278, 269}, {589, 505}, {930}

按次高位分别对上述各子序列排序后得到
{008}, {063, 064}, {083}, {109}, {184}, {269}, {278}, {505}, {589}, {930}

按最低位分别对上述各子序列排序后得到
{008}, {063}, {064}, {083}, {109}, {184}, {269}, {278}, {505}, {589}, {930}

最后再将所有的子序列依次联接在一起就得到排好序的序列
{008, 063, 064, 083, 109, 184, 269, 278, 505, 589, 930}

下面我们描述 M SD 法的一种易于并行化的实现算法. 从上面的例子可以看出,M SD 法实际上是按某个关键字位对当前得到的各个子序列分别进行排序, 而且各个子序列的排序过程可以独立地进行. 假设待排序的 n 个记录存放在数组 R [ 1, …, n ] 中, 排序过程 中出现的各个子序列仍然依次存放在数组 R [ 1, …, n ] 中. 为了对某个子序列排序, 我们需要知道该子序列 在数组 R [ 1, …, n ] 中的起始位置, 该子序列的长度即子序列中记录的个数以及对该子序列进行排序时所 用的关键字位. 为此我们用一个循环队列 Q [ 0, …, n - 1 ] 中存放各个子序列在数组 R [ 1, …, n ] 中的起始位 置, 子序列的长度和对该子序列进行排序时所用的关键字位. 在开始排序时, 仅有一个子序列即给定的记 录序列, 因而初始时队列 Q 中仅存放给定记录序列的起始位置 1, 长度 n , 排序关键字位 1. 在按关键字位 j 对一个子序列排序时, 我们采用下列方法: 首先计数 k ji = t   ( 0 ≤ t ≤ r - 1) 的个数, 将 其记录在数组 NUM [ 0, …, r- 1 ] 的第 t 个单元 NUM [ t ] 中, 并计算关键字位 k ji = t 的第一个记录在该子序 列中的起始位置, 并用数组 PO S[ 0, …, r- 1 ] 的第 t 个单元 PO S [ t ] 记录. 若该子序列在数组 R [ 1, …, n ] 中 的起始位置为 Sta rt, 显然有
PO S [ 0 ]= Sta rt, PO S [ t ]= PO S [ t- 1 ]+ NUM [ t- 1 ],    ( 0≤ t≤ r- 1)

然后依次扫描该子序列, 若当前记录 R i 的第 j 位关键字 k ji = t, 则将 R i 放入辅助数组 B [ 1, …, n ] 的第 PO S [ t ] 个位置, 然后置 PO S [ t ]= PO S [ t ]+ 1. 待按关键字位 j 对各个子序列排好序后, 再将数组 B 写回数组
. R , 这时该子序列已按第 j 位排好序了 对上述方法的一个改进是, 在按关键字位 j 对一个子序列排序时,

首先检查该子序列的第 j 位关键字是否全相同, 若全相同, 则在 j < d 时继续对该子序列的第 j + 1 位关键 字进行排序, 否则用上述方法对该子序列的第 j 位关键字排序.   在下面的算法中, 我们对记录使用了如下的类 Pa sca l 说明:  T yp e N ode = R eco rd
Key= A rray[ 1, …, d ] of 0, …, r- 1; O therfield s; End;    A rrayT yp e= A rray [ 1, …, n ] of N ode; 所用循环队列 Q 的说明如下:

 T yp e Q ueueN ode = R eco rd Sta rt: 1, …, n;
L en: 1, …, n; KeyPo s: 1, …, d ; End; Q ueueT yp e= A rray [ 0, …, n - 1 ] of Q ueueN ode; 在下面的算法中, 我们使用了如下队列操作: In itQ ueue (Q ) : 初始化队列 Q ; EnQ ueue ( Q , Sta rt, L en, KeyPo s) : 将数组 R [ 1, …, n ] 中的起始地址为 Sta rt, 长度为 L en 且当前排序

? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

104

系统工程理论与实践

1999 年 7 月

关键字位为 KeyPo s 的子序列入队. D eQ ueue ( Q , Sta rt, L en, KeyPo s) : 将数组 R [ 1, …, n ] 中的起始地址为 Sta rt, 长度为 L en 且当前排序 关键字位为 KeyPo s 的子序列出队. Em p ty ( Q ) : 判别队列 Q 是否为空;
. M SD 法的一个实现方法由下面的算法 1 形式地给出

算法 1  SD 基数排序算法: M
beg in 1)   in itQ ue ( Q ) ; enqueue ( Q , 1, n , 1 ) ; P rocedu re R ad ix 2So rt (V a r R : A rray T yp e; n : in teger) ; T hen i← i + 1 E lse Equa l←Fa lse; N um [ j ] ←0 ; Po s [ j ] ←0 ; EndFo r Fo r j = Sta rt To Sta rt+ L en- 1 Do Tpo s←0; W h ile N um [Tpo s ]= 0 Do Tpo s←Tpo s+ 1; Po s[Tpo s ] ←Sta rt; If (N um [Tpo s ]> 1) and ( KeyPo s< d ) T hen Fo r j = Tpo s+ 1 To r - 1 Do

2)   h ile N o t em p ty ( Q ) Do W 3)  D equeue ( Q , Sta rt, L en, KeyPo s) ; Equa l←T rue; 4)   h ile Equa l Do W 5)   i ←Sta rt+ 1;

6)   h ile ( i < = Sa trt 2 en+ 1) and (Equa l) Do W L 7)   If R [Sta rt ]. Key [KeyPo s ]= R [ i ] . Key [KeyPo s ] 8)   9)   10) If Equa l T hen 11) If KeyPo s< d T hen KeyPo s←KeyPo s+ 1 12) E lse Equa l←Fa lse; 13) EndW h ile 14) If KeyPo s< d T hen 15)  Fo r j = 0 To r - 1 Do 16) 17) 18) 19) 20) 21) 22) 23) 24) 25) 26) 27) 28) 29) 30) 31) 32) 33) 34) 35) Po s[ j ] ←Po s[ j - 1 ]+ N um [ j - 1 ]; If (N um [ j ]> 1) and (KeyPo s< d ) EndFo r; Fo r j = Sta rt To Sta rt+ L en- 1 Do B [Po s[ R [ j ]. Key [KeyPo s ] ] ] ← R [ j ]; EndFo r; End If;

N um [R [ j ] . Key [KeyPo s ] ] ←N um [R [ j ] . Key [KeyPo s ] ]+ 1;

 Enqueue ( Q , Sta rt, N um [Tpo s ], KeyPo s+ 1) ;

T hen Enqueue (Q , Po s[ j ], N um [ j ], KeyPo s+ 1) ;

Po s[ R [ j ]. Key [KeyPo s ] ] ←Po s[ R [ j ]. Key [KeyPo s ] ]+ 1;

Fo r j = Sta rt To Sta rt+ L en- 1 Do R [ j ] ←B [ j ] ;

? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

第7期
36) EndW h ile; 37) End;

最高位优基数排序的一种实现方法

105

2 算法的正确性证明及算法分析
  定理 1 算法 1 正确地对 n 个记录排序.   证明 我们如下证明算法 1 的正确性, 对于队列 Q 中的任何子序列 S , 若其排序关键字位为 j , 则该子 序列已按关键字位 1, 2, …, j - 1 正确地排序, 且所有不在队列 Q 子序列中的记录已被正确地存放在数组
. R 中, 这样当 Q 为空时, 所有的记录已被正确地存放在数组 R 中了

初始时, 队列 Q 中仅含有一个子序列即给定的待排序的记录序列, 其排序关键字位为 1, 显然该子序 列已按关键字位 0 正确地排序. 在执行 W h ile 循环时, 若一个子序列 S 由语句 3 ) 出队时, 其排序关键字位 为 j , 我们首先看该子序列的第 j 位关键字是否都相同, 若都相同, 则该子序列已按第 j 位排好序了, 当 j < d 时, 我们再按第 j + 1 位关键字对该子序列排序, 当 j = d 时, 则该子序列已排好序了, 这由步骤 4)~ 13) 完 成, 若不完全相同, 则经过步骤 15)~ 29) 后, 该子序列被分为若干子序列 S 1 , S 2 , …, S k ( 0 ≤k ≤ r - 1) , 其中
S i 中记录的第 1, 2, …, j 位关键字相同, 且 S i 中记录的第 j 位关键字小于 S i+ 1 中记录的第 j 位关键字 ( 1≤ i

≤k - 1) , 步骤 30)~ 34) 将子序列 S 1 , S 2 , …, S k 按第 j 位关键字正确地存放在数组 R 中了. 若某子序列仅 有一个记录, 显然该记录在数组 R 中的位置已是该记录在排好序的序列中的最后位置, 若某子序列有多于 一个的记录, 则步骤 24) 、 ) 将该子序列放入队列 Q 中, 下次将按第 j + 1 位关键字对该子序列排序, 当所 28 有子序列都已按关键字位 d 排好序后, 这时队列 Q 为空, 且所有记录都已被正确地存放在数组 R 中了, 这 就归纳地证明了定理 1. 为了分析算法 1 的时间复杂度, 首先估计放入队列 Q 中子序列的个数. 我们可以用一个 r 叉树描述子 序列的产生过程. 例如对于关键字序列{278, 109, 063, 064, 930, 589, 184, 505, 269, 008, 083}, 我们有下列 r 叉树:

每个入队的子序列可以用 r 叉树中的内结点表示, 故要估计入队的子序列的个数, 只要估计内结点的个数 即可.   引理 入队子序列的个数不超过 n - 1.   证明 由算法 1 知, 对于一个子序列, 仅当对当前关键字位该子序列有两个不同的关键字时, 该子序 列才入队, 故 r 叉树中每个内结点至少有两个儿子. 设 r 叉树中度为 0, 1, …, r 的结点个数分别为 n 0 , n 1 , …, n r , 那么有 故有
n 0 + n 1 + …+ n r = n 1 + 23 n 2 + …+ r 3 n r + 1, n 0 = n

于是内结点的个数

? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

n 2 + n 3 + …+ n r ≤n 2 + 23 n 3 + …+ ( r - 1) 3 n r = n 0 - 1= n - 1

n 2 + 23 n 3 + …+ ( r - 1) 3 n r = n 0 - 1,

( 下转第 111 页)

第7期

相似关系的基本概念及其弱等价性质

111

  定理 2 算法 1 的时间复杂度为 O ( (d + r) n ).   证明 算法 1 的时间复杂度由语句 7) , 16) , 31) 所决定. 在每次W h ile 循环中, 当按关键字位 j ( 1≤ j ≤ . d ) 对记录进行排序时, 语句 7) , 30) 最多执行 n 次, 故语句 7 ) , 30) 共执行 O ( d n ) 次 对 Q 中的每个子序列, 语句 15) 执行 r 次, 由引理知, 最多有 n - 1 个子序列入队, 因而语句 16) 最多执行 rn 次, 故算法的时间复杂 度O ( (d + r) n ).

3 结语

在本文中, 我们给出了最高位优先基数排序算法的一个实现方法, 时间复杂度与最低位优先基数排序 算法一样, 同为 O ( (d + r ) n ) , 关于将上述算法扩展为异步并行基数排序算法的研究工作, 我们将另文讨 论.

[ 4 ]  钟安环 1 生物学引论 1 北京: 中国人民大学出版社, 1983 [ 6 ]  张颖清 1 全息生物学 ( 上) 1 北京: 高等教育出版社, 1989

[ 5 ]  许国志等编著 1 系统科学大辞典 1P622 “要素”昆明: 云南科技出版社, 1994 ,

[ 7 ]  梁俊雄 1 全息理论的数学基础 ( 概述) 1 ( 云南省第二届青年学术年会论文集) , 昆明: 云南科技出版

社, 1996

[ 8 ]  尚玉昌等编著 1 普通生态学 ( 上册) 1 北京: 北京大学出版社, 1992 [ 10 ]  邹珊刚等编著 1 系统科学 1 上海: 上海人民出版社, 1987

[ 11 ]   [ 英 ] 肯尼思?法尔科内著, 曾文曲等译 1 分形几何—— 数学基础及其应用 1 沈阳: 东北工学院出版

社, 1991

[ 12 ]  张济忠 1 分形学 1 北京: 清华大学出版社, 1995 [ 14 ]  梁俊雄 1 全息理论的数学基础 ( 11 15 ~ ( 上接第 105 页)

[ 13 ]  敖力布, 林鸿溢主编 1 分形学导论 1 呼和浩特: 内蒙古人民出版社, 1996

[ 1 ]  严蔚敏, 吴伟民 1 数据结构 1 北京: 清华大学出版社 ( 第二版) , 1992

[ 2 ]  施伯乐, 蔡子经, 孟佩琴, 张乃玲 1 数据结构 1 上海: 复旦大学, 1988

[ 3 ]  Knu th D E. T he A rt of P rog ramm ing. So rting and Sea rch ing. 1973, 3

? 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.

) ——全息胚的枝形结构 1 武汉: 华中师范大学学报 ( 专辑) , 1996:

参考文献


更多相关文章:

非常超级学习网 fccjxxw.com

copyright ©right 2010-2021。
非常超级学习网内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图