一种新的表插入排序算法

• 作者: 陈黎静
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 算法 表插入排序 查找 时间复杂度
• 年，卷（期）: 2010,（8）
• 页码范围: 33-36
• 分类号: TP301.6
• 字数: 4177字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2010.08.009

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈黎静	山东科技大学信息科学与工程学院	4	5	2.0	2.0