双向交替折半插入排序法-《计算机技术与发展》

文章信息/Info

作者:: 王代星¹ ; 袁琳琳²; 1. 贵州大学教育教学评估中心、高等教育研究所,贵州贵阳 550025; 2. 贵州职业技术学院,贵州贵阳 550023

Author(s):: WANG Dai-xing¹; YUAN Lin-lin²; 1. Higher Education Evaluation Center & Institute of Higher Education,Guizhou University,Guiyang 550025,China; 2. Guizhou Vocational Technology Institute,Guiyang 550023,China

Keywords:: insertion sort; bidirectional; alternating; binary insertion sort; improved algorithm

摘要:: 提出了一种 2-路插入排序法的改进算法。首先在分析 2-路插入排序算法和其他改进算法的基础上,给出了改进算法的思想、算法描述、算法分析。改进算法通过在待排序序列的两端交替地插入排序,有效地减少了数据移动次数。同时保证两端的有序序列同步增长,排序在序列的中间点结束,有效地避免了 2-路插入排序效率受分界元素影响的缺点。算法的空间复杂度为 O(1) 。实验数据证明,在对随机序列排序时,数据移动次数比折半插入排序降低了 50% 、比 2-路插入排序降低了 25% ;在对正序序列排序时,数据比较次数为 2n-3 次,数据移动次数为 0 次,而 2-路插入排序的数据比较次数为 nlog2 n 次,移动数据为 2n 次;在对逆序数据排序时,相比 2-路插入排序而言,数据比较次数降低了 47.37% ,数据移动次数降低了 25% 。

Abstract:: A new improved 2-way insertion sort algorithm is put forward. Firstly,based on the analysis of the traditional insertion sorting algorithm,2-way insertion sorting algorithm and other improved algorithms,the idea,description and analysis of the proposed algorithm are given. The proposed algorithm effectively reduces the number of data movement by alternately inserting at both ends of the sequence to be sorted. At the same time,it ensures that the ordered sequence at both ends grows synchronously,and the ordering action ends at the middle point of the sequence,and it avoids the disadvantage that the sorting efficiency of 2-way insertion sorting algorithm is affected by the first element. The spatial complexity of the proposed algorithm is O(1) . The experimental data shows that when sorting a random sequence,the number of data moves is 50% less than the binary insertion sort and 25% less than the 2-way insertion sort; when sorting sorted sequence data,the number of data comparisons is 2n-3 times,the number of data movement is 0 times,while the number of data comparisons of 2-way insertion sort is nlog2 n times,and its number of data movement is 2n times; when ordering an inverse ordered sequence,compared with 2-way insertion sort,the number of data comparisons and data movement decreases by 47.37% and 25% .