10.3969/j.issn.1673-629X.2010.08.009
一种新的表插入排序算法
表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O(n2/4).针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析.大量实验表明,新的表插入排序算法的平均时间复杂度为O(n2/6),而查找插入位置所需进行的元素比较的次数平均减少了33%.结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向.
算法、表插入排序、查找、时间复杂度
20
TP301.6(计算技术、计算机技术)
国家自然科学基金60773034;山东科技大学"春蕾计划"项目2008BZC012
2010-09-28(万方平台首次上网日期,不代表论文的发表时间)
共4页
33-36