多路插入排序算法  

Multi-way insertion sort

作　　者：李胜华[1] 

机构地区：[1]湖北大学数学与计算机科学学院,湖北武汉430062

出　　处：《湖北大学学报（自然科学版）》2008年第2期145-148,共4页Journal of Hubei University：Natural Science

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

摘　　要：对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O(n)时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序.For the traditional straight insertion sort which runs in O（n^2） time, a multi-way insertion sort is proposed. The algorithm and its analysis are given. The relation between the number of the ways used in the algorithm and the time complexity is discussed in detail. It shows that the best number of the ways is O（√n）, and the time complexity is O（n^3/2）. Finally, the new algorithm is compared with several existing algorithms, from which it can be seen that our algorithm is more effective. Moreover, our idea can also be applied to the binary insertion sort.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]