任意分布数据的映射归并排序算法研究

摘要：

针对银行业务管理、高考成绩统计、气象资料整理等一类特殊“汇总”排序问题.文中提出了一种以映射、链接和归并为基础的新排序算法映射归并排序算法(以下简称为“映射归并排序”)，给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果.算法分析和实验结果都表明：映射归并排序方法和待排序数据分布无关，其时间复杂度仅为O(N)；而且在处理上述大规模“汇总”排序问题时，映射归并排序速度明显优于Flash Sort、Proportion Split Sort、2-路重复的K路归并排序和直接K路归并排序等算法.

关键词：排序、归并排序、映射、链接

所属期刊栏目：28

分类号：TP302(计算技术、计算机技术)

资助基金：国家自然科学基金69974032

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：8-14