一种新的表插入排序算法

摘要：

表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O(n2/4).针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析.大量实验表明,新的表插入排序算法的平均时间复杂度为O(n2/6),而查找插入位置所需进行的元素比较的次数平均减少了33%.结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向.

关键词：算法、表插入排序、查找、时间复杂度

所属期刊栏目：20

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

资助基金：国家自然科学基金60773034;山东科技大学"春蕾计划"项目2008BZC012

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

页数：共4页

页码：33-36