[1]陈黎静.一种新的表插入排序算法[J].计算机技术与发展,2010,(08):33-36.
　CHEN Li-jing.Improved Algorithm of Linked List Based Insertion Sort[J].,2010,(08):33-36.
点击复制

一种新的表插入排序算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2010年08期
页码:
33-36
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Improved Algorithm of Linked List Based Insertion Sort
文章编号:
1673-629X（2010）08-0033-04
作者:
陈黎静
山东科技大学信息科学与工程学院
Author(s):
CHEN Li-jing
School of Information Science and Engineering,Shandong University of Science and Technology
关键词:
算法; 表插入排序; 查找; 时间复杂度
Keywords:
algorithm;  linked list based insertion sort;  searching;  time complexity
分类号:
TP301.6
文献标志码:
A
摘要:
表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O（n2/4）。针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析。大量实验表明,新的表插入排序算法的平均时间复杂度为O（n2/6）,而查找插入位置所需进行的元素比较的次数平均减少了33%。结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向
Abstract:
The advantage of linked list based insertion sort consists in avoiding record movement,its most spending is to search inserting position,and its average time complexity is O（n2/4）.Every search has to start from the head of the linked list in the algorithm

相似文献/References:

[1]童岚岚 刘连忠.基于动态联盟的一种身份信任计算模型[J].计算机技术与发展,2010,(02):152.
　TONG Lan-lan,LIU Lian-zhong.One of Arithmetic Models of Identity Trust Management Based on Dynamic Federation[J].,2010,(08):152.
[2]邹星.一种基于模板库的车牌字符识别算法[J].计算机技术与发展,2010,(04):128.
　ZOU Xing.A License Plate Character Recognition Arithmetic Based on Template Library[J].,2010,(08):128.
[3]杨明明 王铮.Netfilter性能动态改善方法的研究与实现[J].计算机技术与发展,2010,(04):163.
　YANG Ming.ming,WANG Zheng.Study and Implementation of Algorithm to Dynamic Improvement of Performance of Netfilter[J].,2010,(08):163.
[4]吴长勤 段汉根.基于灰色预测的残缺图像的修复算法[J].计算机技术与发展,2010,(05):124.
　WU Chang-qin,DUAN Han-gen.An Algorithm for Image Reparation Based on Grey Prediction[J].,2010,(08):124.
[5]周佳骏[] 汪婷婷[] 韦刚[].队列遍历算法的加权策略在蠕虫扩散中的应用[J].计算机技术与发展,2009,(05):166.
　ZHOU Jia-jun,WANG Ting-ting,WEI Gang.Application for Weighted Strategy of Queue - Traversal Algorithm in Diffusion of Worm[J].,2009,(08):166.
[6]孙倩 王新华 刘丽.QoS组播路由算法分析[J].计算机技术与发展,2009,(08):96.
　SUN Qian,WANG Xin-hua,LIU Li.An Analysis of QoS Multicast Routing Algorithms[J].,2009,(08):96.
[7]吴晨晖 王映辉.一种基于自顶向下的哈夫曼编码方法[J].计算机技术与发展,2009,(10):50.
　WU Chen-hui,WANG Ying-hui.Huffman Coding Based on a Top- Down Approach[J].,2009,(08):50.
[8]苏成顺 李贞培.基于多线程的分段图像轮廓跟踪算法[J].计算机技术与发展,2009,(10):99.
　SU Cheng-shun,LI Zhen-pei.Algorithm for Multi- Segment Image Contour Following Based on Multithreading[J].,2009,(08):99.
[9]徐军荣 于盛林.提高FMCW雷达测距精度的谱最大值估值算法[J].计算机技术与发展,2009,(04):73.
　XU Jun-rong,YU Sheng-lin.Improving Range Precision of FMCW Radar Using Estimating Maximum Algorithm of Spectrum[J].,2009,(08):73.
[10]边琼芳 邰伟鹏.无向双环网络G（N；±1，±s）的直径求解改进算法[J].计算机技术与发展,2008,(05):135.
　BIAN Qiong-fang,TAI Wei-peng.An Improved Algorithm to Calculate Diameter Undirected Double - Loop Networks G （ N ; ± 1,± s ）[J].,2008,(08):135.

备注/Memo

备注/Memo:
国家自然科学基金（60773034）; 山东科技大学“春蕾计划”项目（2008BZC012）陈黎静（1979-），女，硕士，讲师，研究方向为petfi网理论及应用等
更新日期/Last Update: 1900-01-01