插入排序算法优化①

汪红霞，邵飞飞

(安徽新华学院1.信息工程学院，2.计算机科学与技术学院，安徽 合肥230088)

0 引 言

随着社会的发展，排序作为一种提高查询效率的手段显得越来越重要，尤其是在大数据与云计算广泛应用的今天，大量杂乱无序的信息数据，如果不按照一定的规则排序，会大大降低信息交换工作和查询的效率，因此对排序算法的研究工作存在着一定的实用价值［1～4］.本文主要针对插入排序算法进行优化，研究高效、合适排序算法提升信息交流和查找的效率，减少排序时间.

1 相关工作

近年来，学者们就各种排序算法提出了不同程度的优化，使排序效率有了不同程度的提升，文献［5］仅仅对已有的直接插入排序算法进行阐述及算法分析.文献［6］主要分析了插入排序、选择排序、交换排序，归并排序、分配排序这几种排序的思路，比较了它们之间算法性能.文献［7］主要对直接插入排序、简单选择排序进行程序设计思想、性能指标分析.但是这些优化过的排序算法适用于小数组，对于大量杂乱数据的排序效率并不高.本文主要针对当今社会的庞杂数据应用排序，就直接插入排序算法提出优化思路和改进方案，使其在使用计算机处理规模越来越大的数据的问题上，能够更适应当下技术的发展趋势.

2 排序算法的优化过程

为了能够通过减少交换和比较次数来减少排序时间，本文就插入排序采用随机选取无序区元素、分组、增量、设立标志位等方法进行优化.

2.1 插入排序的优化

直接插入排序法的过程是每次取无序区的第一个元素插入有序区.对排列完全逆序的数组来说，这样固定的选取元素执行插入操作效率非常低.因此，需采用一些策略进行优化.

2.2.1 随机获取无序区元素

使用随机数产生器产生无序区一个数组的下标，如果这个数值小于无序区的第一个数，则交换这两个数，然后按照插入排序将无序区的第一个数插入到有序区.部分代码如下:

2.2.2 分成两组

在2.2.1 中，对无序区采用随机数产生器来获取一个未知大小的数的位置，避免了数组中大量降序排列带来的大量移动.但仅这样做是无法使效率提高到令人满意的水平的，因此在2.2.1 的基础上采用分组策略，即将数组分成两组进行插入排序，然后进行整体插入排序，以达到减少比较移动次数的目的.部分代码如下:

将数组划分为两组再进行插入排序，排序效率提升的幅度不大，故采取多分组的策略对整个数组进行划分.根据测试，当步长为976 时，分组效果最好.因此我们按照976 步长将数组分成若干组，分别对每组进行插入排序，最后再进行一趟插入排序.优化后简略代码如下:

图1 插入排序优化前后的对比

2.2.3 增量策略

增量分组的策略能满足数据量大情况下的排序要求，但这种策略对步长的要求很严格，经过测试，步长最高限定在31250 左右为佳.因此采让步长在31250 的限度下依次递减，每个数组的长度依次增加.简略代码如下:

2.2.4 设立标志位

这种方法的优化思想是:设立一个标志位，标志位用来判断本次快速排序是否产生元素交换，如果没有产生元素交换，即当每个分组都有序时，直接跳出循环.当每个分组都有序时，直接跳出循环.

在数组基本有序的情况下，不必要的比较会产生时间上的消耗，因此设立一个标志位，若本次循环没有发生交换，说明上次循环后，数组已经有序，就跳出循环，进行最后一趟插入排序，简明代码如下:

……//最后再进行一趟插入排序

2.2.5 实验结果

直接插入排序在一种有序数组上的排序效率很高，可以达到10 毫秒以内，而在相反序列的数组上排序效率却很低，在40 万毫秒级左右，由图1 优化前后对比图可以看出，升序数组和降序数组的排序时间都稳定在100 毫秒以内;对于随机数组和重复数组，优化后的插入排序也能够很快将其排列有序，达到了优化前的目标.但分组策略，使得插入排序算法变得不稳定，这也是算法的缺点，还有待改进.

3 结束语

总之，针对在大数据和云计算的应用，本文在直接插入排序算法过程中，采用递归的思想，把大问题分解为小问题，对小数组加以分析针对不同的特点采用不同的优化策略.实验结果表明，优化后的算法在随机数组、升序数组、降序数组和重复数组上的排序比较和移动交换次数，大大缩短了排序时间，提高了排序效率.

［1］ 常璐，夏祖奇.搜索引擎的几种常用排序算法［J］.图书情报工作，2003(6):70－73.

［2］ 张晓刚，李明树.智能搜索引擎技术的研究与发展［J］.计算机工程与应用，2001，37(24):67－70.

［3］ 王晓东.计算机算法分析与设计［M］.北京:电子工业出版社，2009:12－61.

［4］ 于俊超.排序算法在生活中的应用［J］.北京电力高等专科学校学报(自然科学版)，2010，27(6):113－113.

［5］ 李晶.直接插入排序算法分析与实现［J］.中国科技信息，2007(12):347－349.

［6］ 严玮.各种常用排序算法的分析与比较［J］.软件导刊(教育技术)，2013(3):72－74.

［7］ 吴红芝，郭麦成，吴浩.数据结构中内部排序算法的分析［J］.计算机时代，2010(6):38－39.