一种新的表插入排序算法

Improved Algorithm of Linked List Based Insertion Sort

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

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 of linked list based insertion sort,and this case wastes lots of time.In this paper an improved algorithm is proposed that not all searches have to start from the head,and gives an implementation process of material example and its corresponding algorithm analysis.From a great lot of experiment,it is proved that the average time complexity of the improved algorithm is O（n2/6） and the average number of element comparison for searching the inserting position reduces 33%.The result shows that the number of element comparison reduced largely although the time complexity is merely changed.