一种新的排序算法研究

王伟全，陆攀，曹均阔，张学平

一种新的排序算法研究

王伟全，陆攀，曹均阔，张学平

排序是计算机科学中最重要的研究问题之一。介绍了一种新的排序算法，全面深入地分析了挤压式排序的算法思想以及算法实现，并对该算法在时间和空间上的复杂度进行了分析，与快速排序算法、希尔排序算法进行了理论上的对比。理论分析及实验数据表明，该算法是正确的，可行的，在同类排序算法中有明显优势。

挤压式排序；递归；归并；算法

0 引言

排序（Sorting），就是将数据元素（或记录）的一个任意序列，重新排列成一个按关键字有序的序列。由于排序是计算机科学中一项复杂而重要的技术，无论在系统软件还是在应用软件中使用频率都很高[2]，排序算法在最短路径算法中的应用起着关键性的作用，在通信、卫星拓扑网络、地理信息系统（GIS）和计算机网络等的研究和应用中起着基础性的作用[3]。由此可见，排序算法在实际的软件中发挥着重要的作用。

目前已有的排序算法都难以在任何情况下都保持较快的速度，所以对新的排序算法的研究是有实际价值的。性能较优的算法有快速排序、归并排序等，其中快速排序主要运用了递归的思想，归并排序则运用了归并的方法。结合快速排序的递归算法和归并排序的归并思想，本文提出一种新的算法-挤压排序。该算法时间和空间性能较好，在海量数据排序中优势较突出。

1 算法描述与实现

1.1 算法思想

挤压排序，顾名思义就是整个排序过程采用类似“挤压”的方式来实现。该算法融合了递归与归并的思想，具体思想阐述如下：

定义2个数组：Data[1...n]存储待排序的元素，Sorted[1...n]存储已排好序的元素。以下分别简称为D和S。

第一步：通过第一趟排序将待排序数组D分成三个部分，其中两个部分分别存放在数组S的前部和后部，前部元素的值要比后面所有元素的值小，第三个部分覆盖到数组D的前部。

第二步：对数组S的前部和后部进行归并，将归并结果存放在数组S的前部。

第三步：按照此方法对刚刚放在数组D中的第三个部分进行挤压排序，直到数组S中的元素是数组D中的所有元素的有序排列。

1.2 算法推演

为了更直观地描述和分析算法，现以实际数据为例进行算法推演。数组定义见2.1所述，

max、min、unsorted_so_far、sorted_so_far分别记录最大值、最小值、未排序的个数和已排序的个数，假定初始数组D为{34,53,21,78,123,25,110,28,84}，数组S为空。

排序过程:

（1）将数组D分割成3个部分，其中两个部分分别存储在数组S的前部和后部。结果状态为：D{25，110，28，84，123，25，110，28，84}，S{21，null,null,null,null，123，78，53，34}。（分割原则：初始化max=min=D[0],当D[i]＞=max,将该元素在数组S中从下标为n-1向前放,并更新max的值;当D[i]＜min时，将该元素在数组S中从sorted_so_far位置往后放,并更新min的值。当不满足前两个条件时，把该元素在数组D中从下标为0开始存放。）从分割结束的数组D可知，前4个元素没有转移到数组S中，意味着本趟排序操作对这4个元素没有影响，此时unsorted_so_far=4，等待下一趟排序。

（2）对数组S的前部和后部进行归并，以数组D为中介，暂时存放归并结果。归并结束后，将结果复制并覆盖到数组S的前部。结果状态为：D{25，110，28，84，123，78，53，34，21}，S{123，78，53，34，21，123，78，53，34}。此时，由数组S可知，前面5个元素已有序，剩下4个元素待排序。

（3）当上述（2）执行完毕后，第一趟排序结束。然后把步骤（1）所得结果数组D中前4个元素（斜体）依次用上述步骤完成整个挤压排序过程，最后直到unsorted_so_far=0,数组S中的元素即全部有序（S{123，110，84，78，53，34，28，25，21}），排序完成。

2.3 算法实现（C++）

//定义全局变量，分别用于记录待排序的个数，已排好序的个数，未排序的个数

2 算法复杂度分析

2.1 空间复杂度

实现该算法过程中，除数组D外，另外需申请一个数组S，实现该算法需2n的空间,故空间复杂度为O(n)。

2.2 时间复杂度

该算法的时间复杂度主要取决于递归的次数，当不考虑排序时递归的次数，算法的时间复杂度为O(n)。令递归次数为c次，那么c的值可能会根据排序序列的不同而不同。最好情况下为c=0时（即经过0次递归就已经排序完成），例如序列68,72,43,81,88,30,108,12,5,129……，按照此规律排列的数可以不用经过递归就可实现排序（规律：从第一个元素开始一部分元素（斜体）一直递增，另一部分元素一直递减）满足上述规律的数据序列，该算法可以高效地对序列进行排序，时间复杂度为O(n)。最坏情况是每次递归只能挤压两个数，例如序列1，100，2，99，3，98，4，96，5，95……，这种情况下该算法是比较低效率的，时间复杂度为2+4+6+……+(n-2)+n=O(n^2)。

2.3 复杂度对比分析

（1）快速排序

快速排序算法的基本思想：在数组中选择一个轴值，将其它数与轴值比较，比轴值小的数放在轴值左边，比轴值大的数放在右边。于是，数组就分割成了两个子数组，递归执行上述步骤，直到子数组变成两个元素为止。

时间复杂度：最好情况下为O(nlogn)，最坏情况下为O(n^2)。

空间复杂度：需O(logn)的辅助空间。

（2）冒泡排序

冒泡排序算法的基本思想：将被排序的数组D[1...n]垂直排列，每个元素D[i]视为重量为D[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组D，凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

时间复杂度：最好情况下（初始为正序），只需通过n-1次比较，不需要移动关键字，即为O(n)；最坏情况下（初始为逆序），须进行n(n-1)/2次比较，即为O(n^2)[4]。

空间复杂度：整个排序过程为比较交换，需O(1)的辅助空间。

表1 复杂度对比分析情况表

3 算法性能对比分析

对大量数据进行多次测试（数据由随机函数Rand()产生），多次测试结果如下表：

表2 大数据下算法性能测试对比分析情况表

由上表对比实验结果数据分析可得：挤压排序在时间性能上略低于快速排序，但却比冒泡排序快很多。

4 总结

本文研究提出的挤压排序算法是合理的、有效的，具有一定的先进性和应用前景。

[1]霍红卫,许进.快速排序算法研究[J].微电子学与计算机,2002.

[2]周建钦.超快速排序算法[J].计算机工程与应用,2006.

[3]汪维清,罗先文,汪维华.分组排序算法[J].计算机工程与应用,2008.

[4]淦艳,杨有.五种排序算法的性能分析[J].重庆文理学院学报(自然科学版),2010.

[5]Clifford A.Shaffer.Data Structures and Algorithm Analysis in C++[M].北京:电子工业出版社,2013.

Study on a New Sort Algorithm

Wang Weiquan1,Lu Pan2,Cao Junkuo3,Zhang Xueping3
(1.Network Management Center,Hainan Medical University,Haikou 571199,China; 2.College of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,China; 3.College of Information Science and Technology,Hainan Normal University,Haikou 571100,China)

Sorting is one of the most important research problems in the area of Computer Science.In this paper,a new sorting algorithm called Squeeze sort is introduced.There are detailed analyses about the thought of this sorting algorithm and the comparison with Quick sort and Shell sort in theory in the paper.It also gives the algorithm implementation in C++.Both theoretical analysis and experimental tests confirm that Squeeze sort algorithm is correct，feasible and has obvious advantages when compared with other algorithms using similar methods.

Squeeze Sort;Recursion;Merge;Algorithm

TP311

A

1007-757X(2015)06-0061-02

2014.12.07）

王伟全（1984-），男，海南医学院，实验师，学士，研究方向：智能算法、数据库、网络，海口，571199

陆 攀（1996-），男，华南理工大学，大学本科，研究方向：智能算法、数据库、手机应用开发，广州，510006

曹均阔（1973-），男，海南师范大学，副教授，博士，研究方向：智能算法、数据库、嵌入式开发、手机应用开发，海口，571100

张学平（1963-），男，海南师范大学，副教授，学士，研究方向：智能算法、数据库，海口，571100