快速排序算法优化

汪红霞，邵飞飞

（安徽新华学院a.信息工程学院；b.计算机科学与技术学院，合肥230088）

快速排序算法优化

汪红霞a，邵飞飞b

（安徽新华学院a.信息工程学院；b.计算机科学与技术学院，合肥230088）

排序算法的好坏决定着程序运行速度的快慢。为达到提高排序算法效率、减少数据排序时间的目的，从随机选取关键元素、双向索引和小数组插入排序等方面对快速排序算法进行优化。经过测试可知，改进后排序算法的排序效率有很大提高。

快速排序；优化；排序效率

在注重效率的今天，排序作为一种提高查询效率的手段越来越被人们所重视。大数据与云计算广泛应用后，若仅获取到大量的杂乱无序的数据而没有一定的规则来进行排列和查询，会给信息交换工作带来极大不便，因此对排序的研究在理论上和实践上都有重要的价值［1-3］。以往，计算机存储资源的不足制约着程序的排序效率［4］，但是在计算机存储设备急速发展的今天，存储空间已经不是排序算法的局限，只需利用计算机的高速运算能力，再配合高效、合适的排序算法，就能够减少排序时间，使信息交流和查找的效率得到极大提高。

1　相关工作

人们已经改进了多种排序算法，使排序效率有了不同程度的提升［5-6］，例如，对冒泡排序法采用了设立标志位的方法，以减少其排序的循环次数。但是这些优化过的排序算法都只适用于小数组，对大量杂乱的数据排序效率并不高。本文优化快速排序算法，使其适用于处理规模越来越大的数据，符合技术发展的要求。

2　排序算法的优化过程

为了能够通过减少交换和比较次数来减少排序时间，我们对快速排序算法进行了3步优化，即随机选取枢轴、双向索引和小数组插入排序。

因为在原始的快速排序中，每趟排序的枢轴元素都是选取待排序数据区间最前端或者最末端元素，即固定基准点，这样，如果数组是有序的，则排序的时间复杂度就会退化到最坏的情况0（n2），且每趟排序对每个子序列只产生一个有序位置，所以对数组中相等元素的处理效率不是很高。

2.1随机选取枢轴

快速排序在最佳情况下的时间复杂度是O（nlog2n），最坏情况下是0（n2）。在对有序数组排序时，快速排序算法的性能会退化到最坏情况，如利用随机产生器产生一个随机位置作为下标，则可避免因选择固定基准点而产生最坏情况。改进后的代码如下：

2.2双向索引

扫描过程如图1所示。假设数组的前端坐标为p，末端坐标为r，采用两个下标索引i、j分别从数组的首、末两端向中间进行扫描。当i遇到比基准点（即图1（a）中的T）小的元素时，就将此元素与p+1位置的元素进行交换，同时p加1；当j遇到比基准点大的元素时，就将此元素交换至r位置，同时r减1。这一过程直到当j小于等于i时停止。这样，最终的划分点便落在j，再将基准点交换到j上，用以上方法递归排序j点左右两端的子序列，以此类推，直至排序完成。

图1　扫描过程

2.3小数组插入排序

插入排序的时间复杂度是0（n2）；但是对有序排列的数组，插入排序的最佳情况是0（n）。插入排序中包含的常数因子使得当n较小时，算法运行得较快。因此，当数组递归子序列的规模在一个固定阀值（阀值指数组的最大长度）以下时，采用插入排序对子序列进行排序，能够缩短排序时间。测试结果表明，阀值在7个元素左右时效率较高。改进后的代码如下：

2.4实验结果

图2为数据规模n为50万个元素时，快速排序优化前后的对比图。从图2可以看出，优化后的排序时间比优化前大大缩短，排序的效率大大提升。

图2　快速排序优化前后对比

3　结束语

针对排序的比较次数和移动交换次数，文中讨论了快速排序算法以及插入排序算法的优化策略，对比了算法优化前后的排序时间。结果表明，优化后的算法对各种数组的排序效率很高，符合目前对效率的要求，达到了优化的目的。

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

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

［3］文军，孙宏，徐杰，等.基于排序算法的机场停机位分配问题研究［J］.系统工程，2004（7）：102-106.

［4］蔡炳育，陈慧贤.云计算与数字资源存储问题分析［J］.巢湖学院学报，2009（6）：27-30.

［5］严蔚敏，吴伟民.数据结构［M］.北京：清华大学出版社，2009：265-279.

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

【责任编辑梅欣丽】

Sorting Algorithm Optimization

WANG Hongxiaa，SHAO Feifeib
（a.Institute of Information Engineering；b.School of Computer Science and Technology，Anhui Xinhua University，Hefei 230088，China）

Nowadays，cloud computing and big data more and more attention，and time as a measure of the efficiency factor，will increasingly need to be resolved，ranking algorithm determines the running speed of the program.In order to improve the operating efficiency of sorting algorithms，reduce sorting time for large amounts of data，quickly sort algorithms from random key elements，bidirectional index，small array insertion sort to optimize.After the test，improved sorting algorithm sorting efficiency is greatly improved.

quickly sort；optimize；sorting efficiency

TP39

A

2095-7726（2015）09-0033-03

2015-07-01

汪红霞（1979-），女，安徽宣州人，讲师，硕士，研究方向：计算机技术。