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

一种新的排序算法研究

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

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

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

0 引言

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

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

1 算法描述与实现

1.1 算法思想

挤压排序，顾名思义就是整个排序过程采用类似“挤压”的方式来实现。……