多路插入排序算法

摘要：

对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O√n时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序.

关键词：直接插入排序、多路、算法、时间复杂性

所属期刊栏目：30

分类号：TP301.6(计算技术、计算机技术)

资助基金：湖北省教育厅重点项目D200710001

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

页数：共4页

页码：145-148