关于数据分类的一个新的有效算法

D0I:10.13374/j.issn1001-053x.1985.03.022 北京钢铁学院学报 1985年第3期 关于数据分类的一个新的有效算法 软件工程教研室李辉华 摘 要 本文提出了一种渐的分类算法，该算法特别适用于分类元素关健字值重复性 较高的元素集。新算法采用了我们称之为单指针队列移动的思想，通过扫描全部元 素一遍或二遍便将其分类完。当对关键字值仅有M种的共N个元素分类时，新算 法的排序效率，即总的比较次数为O(NLOG2M),元素总移动次数为O(MN),所 需附加空间为M个指针单元和M个存关键字值单元。在极端情况下，即M与N相 等时，以上时空效率的形式不改变。 约定：若元素a和b具有相同的关能字值，则称元素a和b是同类元素。反之， 亦然。 一、问题的提出 我们知道，计算机的很多运行时间耗费在分类(Sorting)上。在对元素进行分类时， 时常遇到一类特殊问题一当元素集中，元素种类数较少时，如何尽快地将其分类？若利用 现存的较好的分类算法，诸如希尔分类法，堆分类法、快速分类法和归并分类法，那么，分 类N个元素需时O(N·1og2N),需要附加空间从1个单元到N个单元不等（依次为1、1、 1og2N和N)。这些算法均未利用元素之种类数较少这一特性来改善算法的时空效率。 二、算法的设计基础和思想 本算法充分利用了元素之种类数较少，或者说元素的关键字值重复性较高这一特性，采 用了一种称之为单指针队列的数据结构，并且用一数组向量记下每一种类元素的关健字值 以便查对。从总体上看，木算法可分成三个组成部分： (1)输入待分类元素，用数组按分类次序记下每一孙类元素之关键'宁值，即建立关健 字值数组。 (2)通过一遍扫描将元素分类完毕。 (3)输出分类结果。 在说明各部分的设计思想之前，我们先介绍本算法用到的数据结构。 90

北 京 钢 铁 学 院 学 报 年 第 期 关于数据分类的一个新的有效算法 软件 工 程 教研 室 李辉 华 摘 要 本文 提 出 了一 种 新 的 分 类算 法 ， 该 算 法 特别 适 用 于 分 类元 素 关键 字值 重 复性 较 高的 元 素集 。 新 算法 采 用 了我们 称 之 为 单 指 针队 列移 动 的 思 想 ， 通 过 扫 描 全 部元 素一 遍 或 二 遍 便 将 其分 类完 。 当 对 关键 字 值 仅 有 种 的 共 个 元 素分 类时 ， 新 算 法 的排 序 效率 ， 即 总 的 比 较次 数 为 ， 元 素 总移 动 次 数 为 ， 所 需附 加 空 间为 个指 针单元 和 个 存 关键 字值 单 元 。 在极 端 情兄 下 ， 即 与 相 等时 ， 以 上 时 空 效率 的 形 式 不 改 变 。 约定 若 元 素 和 具 有相 同的 关键 字值 ， 则 称 元 素 和 是 同 类元 素 。 反之 ， 亦 然 。 一 、 问题 的提出 我们知道 ， 计 算机的很 多运行 时 间耗 费在分 类 匕 。 在 对元 素进行分 类 时 ， 时常遇 到一 类特殊 间题 一一 当元 素集 中 ，元素种 类数较少 时 ， 如何尽 快地 将其分 类 若利 用 现存的较好的分 类算法 ， 诸 如希尔分 类法 、 堆分 类法 、 快速分 类法 和归并分 类法 ， 那 么 ， 分 类 个元 素需 时 · ， 需要 附加 空 间从 个单元 到 个单元 不等 依 次为 、 、 和 。 这些 算法 均未利用元素之种 类数较少这一 特性 来 改 善 算 法 的时空效率 。 二 、 算法 的设计基础和思想 本算法充分 利 用 了元素 之种 类数 较少 ， 或 者说元 素的关键 字值重 复性较高这 一特性 ， 采 用 了一种称 之为单指针队 列的数据结构 ， 并且 用一数组 向量记 下每 一种 类元素的关键 字值 以便查对 。 从 总体上看 ， 木算法 可分成三个组 成部分 输入 待分 类元 素 ， 用 数组 按分 类次序记 下每一 种类元 素之关键 ‘ 笋汽 ， 即建 认关键 字值数组 。 通过一遍 扫描 将元素分 类完毕 。 输 出分 类结 果 。 在说 明各部分的设计 思想 之前 ， 我们先介绍本算法用到 的数据结构 。 DOI ：10．13374／j ．issn1001－053x．1985．03．022

变量MN:分别代表实际的元素种类数和元素的总数，数组A〔1：N):长度为N, 初始时装待分类元素，算法执行完后装已分类的N个元素。 数组VALUE〔1：M〕：关键字值数组，按分类次序存贮每一种类元素之关键字值， 即满足：VALUE Ci)<VALUE〔i+1〕，1≤i≤M-1。数组P〔1：M):指针 数组，指针P〔i〕指向当前第种元素形成的队列之队头元素位置。 变量POIN T:指针，指向当前正扫描到的待分类元素。 现分别介绍各部分设计思想。 (1)输入待分类元素，建立关键字值数组VALUE,并给指针数组P赋初值。 在这一部分中，先读人全部元素放于数组A中。然后扫描N个元素一遍，每扫描到一 个元素，就采用折半查找方法查找值数组VALUE,判断该元素是否是新的一类元素，即 是否有新的关键字值，若是，将其关键字值按分类次序插入到值数组VALUE中适当位置， 并将种类数M增1。全部元素扫描完后，置HM=(M+1)DIV2,置P〔i)=O(1≤ i≤HM),置P〔i)=N+1(HM+1≤i≤N),置指钋PO1NT=1。 (2)通过一次扫描将元素分类完毕。 当指针POINT<指针P〔HM+1〕时，循环执行下列操作（见图一、二）： D扫描元素A〔POINT〕，置X=A〔POINT),利用折半查找法查找值数组判断该 元素所属种类。若其属于第I种元素，即VALUE〔I〕=A〔POINT)。KEY, 那么，如果I≤HM,转②步。否则，则转③步。 ②置K:=HM,当I≤K时，循环执行下列操作：将指针P〔K〕往后移动一个位置， 即增1，再将第K种元素所对应的队列K之队尾元素移至指针P〔K〕所指位置，即 A〔P〔K)):=A〔P〔K-1)+1),然后置K:=K-1,继续循环。循环 结束后，将指针P〔I〕后移一个位置，将正扫描到的元素A〔POINT)（保存在X 中)送入P〔I)所指位置，即P〔I〕·=P〔I)+1,A〔P〔I)):=X,然 后将指针POINT后移一个位置，扫描下一个待分类元素。 ③置K:=HM+1,将A〔P〔K)一1〕送A〔POINT〕（新的待分类元素）， 然后，循环执行下列操作直至I≤K：将指针P〔K〕往前移动一个位置，即减1，将第K 种元素所对应的队列K之队尾元素移到P〔K〕现在所指位置，即P〔K):=P〔K) -1,A〔P〔K)):=A〔P〔K+1)-1〕，再置K:=K+1,继续循环。循环 结束后，将指针P〔【〕往前移动一个位置，再将当前正扫描到的元素X送入指针P〔I)所 指位置，即P〔I：=P〔I)-1,A〔P〔I〕)：=X,然后，指针POINT不变，继 续扫描“下一个”待分类元素。 (3)输出分类结果 将现在数组A中的元素输出，即得分类结果。 A(I 待分类元素 A(N) 介 P1,P2,…PHM,值为0。 PHM+I,…PM,值为N+1e (图一)初始状态时 91

变量 、 分别 代表实际的元素种类数和元素的总 数 。 数组 〔 〕 长 度为 ， 初 始时 装 待分 类元 素 ， 算法 执行 完 后 装 己分 类的 个元素 。 数组 〔 〕 关键字值数组 ， 按分 类次序存贮每一种 类元素之关键字值 ， 即满 足 〔 〕 〔 〕 ， 簇 镇 一 。 数组 〔 〕 指 针 数组 ， 指针 〔 〕 指 向 当前 第 种元 素形 成的队 列之队 头元 素位 置 。 变量 指针 ， 指 向当前正 扫描 到的 待分 类元 素 。 现分别 介绍 各部分 设计 思想 。 输入 待分 类元素 ， 建 立 关键 字值数组 ， 并给指针 数组 赋初值 。 在这 一部分 中 ， 先读 入 全部元素放于数组 中 。 然后 扫描 个元素一 遍 ， 每 扫描 到一 个元 素 ， 就 采用折 半查找方法 查找 值数组 ， 判 断该元素是 否是 新的 一 类元素 ， 即 是 否有新的关键 字值 ， 若是 ， 将其关键字值按分 类次序插 人到 值数组 中适 当位置 ， 并将种 类数 增 。 全部元素 扫描完后 ， 置 ， 置 〔 〕 《 ， 置 〔 〕 《 簇 ， 置 指针 。 通 过一 次 扫描 将元 素分 类完毕 。 当指针 指针 〔 〕 时 ， 循环执行 下列操作 见 图一 、 二 ①扫描元 素 〔 〕 ， 置 二 〔 〕 ，利用折半查找法 查找值数组判 断该 元 素所 属种 类 。 若 其属于第 种元 素 ， 即 〔 〕 二 〔 〕 。 ， 那 么 ， 如果 簇 ， 转②步 。 否 则 ， 则转③步 。 ②置 二 ， 当 时 ， 循环执行 下 列操 作 将指针 〔 〕 往后 移动一个 位置 ， 即增 ，再 将第 种元素所对应 的队 列 之队 尾元 素移至 指针 〔 〕 所 指位 置 ， 即 〔 〔 〕 〕 〔 〔 一 〕 十 〕 ， 然后置 二 一 ， 继 续循环 。 循环 结 束后 ， 将指针 〔 〕 后移一 个位置 ， 将正 扫描到的元 素 〔 〕 保 存在 中 送 入 〔 〕 听指 位 置 ， 即 〔 〕 〔 〕 ， 〔 〔 〕 〕 二 ， 然 后 将指针 后移一个 位置 ， 扫描 下一 个待分 类元素 。 ③ 置 二 ， 将 〔 〔 〕 一 〕 送 〔 〕 新的 待分 类 元 素 ， 然 后 ， 循 环 执行 下 列操 作直至 将指针 〔 〕 往前 移动 一个位置 ， 即减 ， 将第 种元 素所 对应的队 列 之队尾元 素移 到 〔 〕 现 在 所 指 位 置 ， 即 〔 〕 〔 〕 一 ， 〔 〔 〕 〕 二 〔 〔 〕 一 〕 ， 再置 ， 十 ， 继续循 环 。 循 环 结 束后 ， 将指针 〔 〕 往前移动 一个位 置 ， 再 将 当前正 扫描 到的元 素 送 入 指针 〔 〕 所 指位置 ， 即 〔 〕 〔 〕 一 ， 〔 〔 〕 〕 ， 然后 ， 指针 不 变 ， 继 续扫描 “ 下一 个 ” 待分 类元素 。 输 出分 类结果 将现在数组 中的元 素输 出 ， 即得分 类结 果 。 仁 、沙 〔 〕 待分 类元 素 仓 ， ， … 。 、 ， 值为 。 。 。 、 ， 仑 … ，，， 值为 图一 初 始 状 态时

往后→ ←往前 h〔1) 尾（队列1）头 Point ACN) L尾（队列Hm)头 L头（队列Hm十1）尾 头（队列m)尾： 均为第一种元紫 均为第Hm种元素 均为第Hm千1种元素 均为第如 分 种元恭 PHm-上 PHm 案 PHe+1 PHm+2 (图二)正在分类时 三、算法分析 ①分类效率 分类效率既是元素分类时平均比较次数。山算法不难得出，在建立关键字值数组VAL UE时，所需比较次数为N·LOG2M,这是因为对M个已分类数据采用折半查找法查找指 定元素或判别其不在值数组中所需比较次数为LOG2M。在执行算法第(2)步判断一个 元素所属种类时，需LOG2M次比较，N个元素共需(N·LOG2M)次比较。综上所述， 本算法，总的比较次数为O(NLOG2M),排序效率为O(NLOG2M)。 ②每一项移动的平均次数 在建立关键字值数组VALUE时，在最坏情况下，关键字所需移动的总次数为M(M- 名一1 1)/2（-)。不尖一般性，假设每一元素在数组A中任何位置出现是等概率的，即 P;=1/N。那么，在执行算法第(2)步时，若每一个元素属于任何一类元素是等概率 的，即q1=1/M,则分类一个元素所需移动元素的次数为：M/4。这由下式推得， 2 j= M (这里P,=,1=1/M) 在最坏情况下，即元素堆集在两头，其关键字或者较大或者较小时，不难推导出每分类一 个元素所需移动元素的次数为M/2。 综上所述，分类M种共N个元素所需移动元素的总次数为O(M·N),所移动关键 字的总次数为O(M2)。 ③附加空间 本算法所需附加空间取决于分类元素的种类数M。具体米说，需M个指针单元，M个 元素关键字单元。因此，当每一个元素所占空间远大于其关键字和指针所占的空间时，本 算法就更加适用。 从算法可以推得，当分类元素按关键字值服从正态分布时，或者元素堆集在中间时， 调用本算法分类这些元素所需移动元素次数会减少。另外，若我们初始已知元素的种类数 92

往后叶 朴在前 层 队列 二 头 －一 一 均为第 种－元素 头 队列 二 尾 〔 〕 头 队列二 尾 ， 」勃履而 一一 种元索 均 为第 种元素 元素分类待 一爪 ” 功 一 二 ” … … …” 口 图二 正 在分 类时 三 、 算法分析 ①分类效率 分类效率既是元素分类时平均比较次 数 。 由算法 不难得 出 ，在建立关键字值数组 时 ， 所需比较次数为 · ， 这是 因为对 个己分类数据采用折半查找法 查找指 定元素或判别其不在值数组 中所需比较次数为 。 在执行算法第 步判 断一 个 元素所 属种类时 ， 需 次 比较 ， 个元素共需 · 次 比较 。 综 上所述 ， 本算法 总的比较次数为 ， 排序效率为 。 ②每 一项移动的平均次数 在建立 关键字值数组 时 ， 在最坏情况下 ， 关键字所需移动的总次数为 。 不失一般性 ， 假设每一元素在数组 中任何位置 出现 是 等概率的 ， 刹玖 即 。 那 么 ， 在执行 算法第 步 时 ，若每一 个元素属于任何一 类元素是 等 概 率 的 ， 即 二 ， 则分类一个元素所需移动元 素的次 数为 。 这 由下式推得 ， 竺 三 〔 ，叠 乙 一 瞥 ， 〕 ‘ 。 。 竺 一 一 ， 、 、 ‘ ，，， 。 、 〕玉 且兰 下节 ， 、 了竺 、 、‘ ， 在最坏情况下 ， 即元素堆集在两 头 ， 其关键 字或者 较大或 者较小时 ， 不难推导 出每分类一 个元素所需移动元素的 次 数为 邝 。 综上所述 ， 分类 种共 个元素所需 移动元 素的总次 数为 · ， 所移 动 关 键 字的总次数为 “ 。 ③附加空间 本算法 所需附加空 间取 决于分 类元素的种类数 。 具体来说 ， 需 个指针单元 ， 个 元素关键 字单元 。 因此 ， 当每一个元 素所 占空 间远 大于其关键字和指针所 占的空 间时 ， 本 算法就更加适 用 。 从算法可 以推得 ， 当分类元素按关键字值服从正 态分布时 ， 或者元素堆集在中间时 ， 调用本算法分类这些 元素所需移动元 素次数会减少 。 另外 ， 若我们初始已知元素的种 类数

及每一种类元素之关键字值，那么我]就可以免做建立关键宁值数组VALUE的工作，从 而减少木算法总的比较次数和关健字的移动次数。 四、试验 按下式取值：A〔I).K上Y=abs(XxmoDM),(【=1…N) Xxt=（25·Xx+525)MOD1021。LI表示本算法。heap表示堆分类法。quick表示快 速分类法。 :移尚次支/10) (比款次数/10) 7 N=8:0G =8138 2 heap hc-- LI qu. 50 100150200M 40 5前100150200 图1（关健字移动次数） 图2 (比较次数/10) N=16876, (移动次数10) 18 N=16376 16 quick 14 12 12 10 LI 10 8 hea p -n heap qvick 102000400M 100200300400M 图3（关键字移动次数） 图4 93

及每一 种 类元 素之关键 字值 ， 那 么我 们就 可以 免做建立关键字值数组 的工作 ， 从 而 减 少 本算法 总的 比 较次 数和 关键 字的 移动 次数 。 按下式 取 值 〔 〕 四 、 试 验 ‘ 、 · 二 。 速 分 类法 。 表示本 算法 。 … 表示 堆分类法 。 表示 快 比较次数 勺 移功 次 支 ‘ ’ 二 八公 内八 衬︸， 一 ‘， 咋日 岌 石 工 图 御场 图 关键 字移动 次数 叱比较次敛 心 ” 二 ‘ ，‘ ’ 厂侈动火州 ， 考 ‘ 冬 卜‘ 执 图 一一 一二 ‘ “ 飞 喻 ， 飞色了廿广肃 户 关键 字移动 次数 召 图

五、程序清单 procedure li; type kind=record key integer;.....end; vara:array〔l…n)of kind;p,value:array(1…maxm〕of integer, kx,h,i,j,k,1,hm,mid,m,n,point,c:integer;x kind, begin input data m:=1 value〔1J:=a〔1)，key, for i:=2 to n do begin kx:=a(i).key;1:1;h:=m while (1<=h)do begin mid;=(1+h)div2;if (kx<value[mid )then h mid-1 else 1:=mid+1 end; if(h=0)then c:=0 else begin if (kx=value (h )then c:=1 else c:=0 end, if (c=0)then begin forj:=m downto1 do value〔j+1〕：=value〔j),m:=m+l, value〔l):=kx end end, hm:=(m+1 div2;point;=1; fori:=1 to hm do p〔i〕：=0 for i:=hm+1 to m do p〔i〕：= n+1 while point<p(hm+1 )do begin l:=1,h:=m影x:=a〔point〕y while (I<=h)do begin mid;=(1+h)div2; if (x,key<value mid )then h:=mid-1 else 1,mid +1 end; i,=hy if (i<=hm then begin k:=hm; while (i<k)do begin p〔k):=p〔k〕+1，a〔p〔k)〕：=a〔p〔k-1〕+1〕，k,=k-1 end; p〔i〕：=p〔i〕+1；point::=point+1,end else begin k:=hm+1;a〔point〕：=a〔p〔k)-1〕， while (k<i)do begin p〔k〕：=p〔k)-1sa〔p〔k〕〕：=a〔p〔k+1)-1),k:=k+1 94

五 、 程序清单 … … 〔 ， 二 〕 ， 〔 … 〕 ， ， ， ， ， ， ， ， ， ， ， ， ， 二 〔 〕 〔 〕 ， 〔 〕 ， ， 二 〔 〕 一 二 〔 〕 ， 〔 〕 〔 〕 ， ， 〔 〕 〔 〕 二 〔 〕 〔 〕 ， “ 〔 〕 ， ， 〔 〕 一 ， ， 二 〔 〕 〔 〕 〔 〔 〕 〕 〔 〔 一 〕 〕 ， 二 一 〔 〕 〔 〕 二 多 〔 〕 〔 〔 〕 一 〕 〔 〕 〔 〕 一 〔 〔 〕 〕 二 〔 〔 〕 一 〕 ， 二

end;p〔i〕：=pri〕-1end a〔p(i):=x end, output data end. 注：冯克清.贺津江同志和教研室其他同志对本文提出了许多宝费意见，在此致谢。 A New Efficient Algorithm For Internal Sorting Li Hui Hua Abstract In this paper,a new internal sorting algorithm is presented which is espe- cially suited for sorting record set in which the total number of key values is much smaller than that of records Viz.many records have the same value. If we assume the total number of records to be sorted is N and the total number of key values is M,the sorting efficiency-the total number of compar- isons-of classical algorithms (e.g.quicksort,heapsort)is O(Nlog2N), unrelated to M.Under the same assumption,the sorting efficiency of the new al gorithm presented in this paper that uses one kind of queue with single pointer data structure,through two passes,is 2'N'log2M,If some conditioing are added,only one pass is needed and the efficiency is Nlog2 M.The moving total number of the new algorithm is N'M/4,and the extra memory space required is M,pointers and M key value locations, 。 95

门‘ ， 〔 〕 〔 卜 ， 〔 〔 〕 〕 注 冯克清 ， 贺幸江 同志和 教研室其他同志对本文提出了许多宝贵意见 ， 在此致谢 ， ， 一 － ， ， 。 ， ， ， ， ’ ，