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

来源期刊：工程科学学报1985年第3期

论文作者：李辉华

文章页码：90 - 95

摘    要：本文提出了一种新的分类算法,该算法特别适用于分类元素关键字值重复性较高的元素集。新算法采用了我们称之为单指针队列移动的思想,通过扫描全部元素一遍或二遍便将其分类完。当对关键字值仅有M种的共N个元素分类时,新算法的排序效率,即总的比较次数为O（N LOG₂M）,元素总移动次数为O（MN）,所需附加空间为M个指针单元和M个存关键字值单元。在极端情况下,即M与N相等时,以上时空效率的形式不改变。 约定:若元素a和b具有相同的关键字值,则称元素a和b是同类元素。反之,亦然。