一种基于有序双端链表的高效排序算法

谭 林，廖光忠

（1.武汉科技大学计算机科学与技术学院，湖北 武汉，430065；2.武汉科技大学智能信息处理与实时工业系统湖北省重点实验室，湖北 武汉，430065）

排序是计算机程序设计中的一项重要操作，它的功能是将乱序的数据元素按照一定的顺序重新排列以减少每次数据访问所消耗的时间和资源。排序算法可分为比较排序算法和非比较排序算法。在非比较排序算法中，由于数据元素的关键字本身就含有了定位特征，因而不需要比较就可以确定其前后位置。适应性更强、应用更广的比较排序算法则是通过对一个抽象内容的比较操作来确定两个数据元素的前后顺序，该算法的唯一要求就是操作数满足全序关系。比较排序算法中，在最好情况下的时间复杂度为O（n），在最坏情况下的时间复杂度为O（n2），其中效率比较高的算法有快速排序、归并排序和堆排序，它们的平均时间复杂度均为O（nlog2n）［1－3］。

本文提出一种新的基于有序双端链表的排序算法，即 ODListsort（ordered double－end linked list sort）算法。该算法是基于元素以链表形式进行动态内存分配的比较排序算法，主要由计算链表最大数量、插入操作和合并链表3个部分组成。本文首先介绍ODListsort排序算法的操作流程，然后分析其时间复杂度，最后通过数据测试实验对该算法和几种经典排序算法的性能进行比较。

1 ODListsort算法

ODListsort算法具体包含3个部分，分别是计算链表的最大数量、链表的双端插入操作以及相邻链表的合并操作。整个排序过程就是将元素按照一定规则插入到链表中，然后合并这些链表，如此反复地插入、合并直至生成一个包含所有元素的有序链表。

1.1 计算链表最大数量

链表的数量会随着数据范围的不同而改变，为了降低算法的时间复杂度，这里首先定义一个可共存的链表最大数量L，当现存链表数量达到L时就要执行链表的合并操作，这样做的好处是，使合并过程中的链表节点数差距不大从而减少比较次数。

L通过create（）函数计算。将需要进行排序的元素数量n传递给create（）函数，函数返回计算出的L值。create（）函数的伪代码如下，其中t为自定义变量，其取值是根据实验反复测试得到的。

1.2 插入操作

一般情况下，插入操作会打乱先前已排好序的数据，所以每次插入元素之后都必须进行一次重排序，增加了许多重复操作，消耗大量时间［4］。因此，在ODListsort算法中加入了插入规则，使得每次插入操作后均保持原链表有序。此时的链表就像一个双端数列，数据可以从两端插入［5］。插入操作和链表的生成过程是同时进行的。

具体插入规则为：将要插入的元素与链表中第一个和最后一个元素进行比较，如果插入元素比链表第一个元素更小，则该元素插入到链表第一个元素的前面；如果插入元素比链表最后一个元素更大，则该元素插入到链表最后一个元素的后面；否则，建立一个新的空链表，并将该元素插入到新建链表里面。因为每次插入都会与链表第一个和最后一个元素进行比较，所以即使插入了新的元素也可以保持原链表有序，无需对链表重新排序。

下面以一个包含10个元素的数据集｛4，0，13，25，99，1，20，22，15，19｝来说明插入操作和链表的生成过程：①新建一个空的链表list 1并插入元素4；②插入元素0，因为0＜4，将元素0插入到链表list 1的头部；③插入元素13，因为13＞4，将13插入到链表list 1的尾部；④重复插入元素25、99；⑤插入元素1，因为99＞1＞0，根据插入规则需要另外新建一个空链表list 2并插入元素1，这样就建立了两个链表；⑥继续插入操作到元素15的时候，又出现与元素1相同的情况，再次建立一个空链表list 3并插入15；⑦插入元素19。最后完成插入操作后总共生成了3个链表，如图1所示。从图1中可以看到，这3个链表都是有序的，所有链表的第一个元素均按照升序排列，所有链表的最后一个元素均按照降序排列。

插入函数list＿insert（）的伪代码为：

图1 生成的链表Fig.1 The generated lists

1.3 合并链表

当数据插入完成后进行合并操作，合并时以递归的方式将所有链表合并成一个［6］。最后一个链表命名为final＿list，将final＿list与其前一个链表previous＿list进行合并形成新的final＿list，如此反复直到所有的链表都合并成一个final＿list。以下是合并函数list＿merge（）的伪代码。

2 ODListsort算法的时间复杂度

排序算法的性能指标有时间复杂度和空间复杂度，随着计算机硬件的升级，内存资源变得越来越丰富，排序算法的空间复杂度已经不是一个太大的问题［7］。因此，本文重点对ODListsort算法的时间复杂度进行计算分析。

2.1 最好时间复杂度

当有n个元素的数据集已经按照升序或者降序排列好的时侯，ODListsort算法具有最好时间复杂度。因为此时ODListsort算法只需要进行插入操作，只会新建一个链表，不需要后续的合并操作，故该算法的最好时间复杂度为O（n）。很明显，在这种情况下，ODListsort算法要优于快速排序和归并排序算法。最好时间复杂度Tb的计算公式为：

2.2 平均时间复杂度

ODListsort算法的平均时间复杂度计算是建立在随机数据集上的。假设数据量为n，实际排序过程中生成的链表总量为K，可共存链表的最大数量为L，通常情况下，n≫K≫L。例如，对于一个有100000个随机数的数据集，通过实验可以发现，K值约为2000，L值为50～85。

用Ta表示平均时间复杂度。在一次完整的插入过程（即生成L个链表）中，所需要的比较次数为：

因为生成L个链表的次数总共为K／L次，所以插入比较的总次数为：

因此，对于整个插入操作，时间复杂度为O（KL）。

对于合并操作，在平均情况下，n个元素被插入到K 个链表中，即每个链表有n／K个元素，对于L个链表的一次合并过程所需要的比较次数为：

因为在对L个链表进行第一次合并之后，再生成L－1个链表才进行第二次合并，所以总共需要的合并次数为K／（L－1），那么合并操作的总比较次数为：

因此，合并操作的时间复杂度为O［nK／（L－1）］。

因为插入操作的时间复杂度为O（KL），与n无关，且远小于合并操作的时间复杂度，因此ODListsort算法的平均时间复杂度就为合并操作的时间复杂度O［nK／（L－1）］。

2.3 最坏时间复杂度

首先举例说明一种极端情况，当出现类似｛0，9，1，8，2，7，3，6，4，5｝的最坏数据集的时候，一次插入过程会生成5个链表，其中每个链表仅包含2个元素。对于有n个元素的数据集，一次插入过程最多生成L个链表，一次合并过程要合并L个链表，如果实际运算过程中生成的链表总数为K，则插入操作和合并操作的总次数均为K／L，但在最坏的情况下，每个链表仅仅包含2个元素，故K＝n／2，因此插入操作和合并操作的总次数均为n／（2L）。

用Tw表示ODListsort算法的最坏时间复杂度。在最坏的情况下，一次插入过程中的比较次数为：

因此，对于整个插入操作，时间复杂度为O（nL）。

从最后一个链表到第二个链表的合并过程中的比较次数为：

n／（2L）次合并过程中，每一次合并L个链表的比较次数均为Tw（merge’）加上最后合并第一个链表的比较次数。

第1次合并L个链表的时候，因为第一个链表只包含2个元素，链表头尾本来就是有序的，不需要再比较两个链表的第一个元素和最后一个元素，所以比较次数为1，则第一次合并的比较次数为：

在第2次合并L个链表的过程中，首先合并含有2个元素的L－1个链表需要比较L（L－1）次，然后将合并后的L－1个链表与第一次合并L个链表得到的链表进行合并，比较次数为两个链表的元素和，总的比较次数为：

故合并操作的时间复杂度为O［n2／（4L）］。

由于插入操作的时间复杂度O（nL）远小于合并操作的时间复杂度O［n2／（4L）］，所以 ODListsort算法的最坏时间复杂度为O［n2／（4L）］。

3 排序实验与结果分析

本实验采用的硬件平台为Pentium（R）Dual－Core E54002.70GHz，2G 内存，软件平台为Windows 7操作系统，Dev C＋＋5.0集成开发环境，数据由随机数生成器产生。

采用插入排序、选择排序、冒泡排序和ODListsort排序算法对包含5×103～105个随机数的数据集进行排序，结果如表1所示。

表1 ODListsort排序与插入排序、选择排序和冒泡排序的比较Table1 Comparison of ODListsort，insertion，selection sort and bubble sort

由表1可见，ODListsort排序算法所消耗的时间比其他3种排序算法所消耗的时间少很多，而且数据量越大，这种时间差距越大。

采用快速排序、归并排序和ODListsort排序算法对包含104～4×105个随机数的数据集进行排序，结果如表2所示。

表2 ODListsort排序与快速排序和归并排序的比较Table2 Comparison of ODListsort，quick sort and merge sort

由表2可见，当数据量为104～105时，3种排序算法的性能非常接近；当数据量为2×105～4×105时，快速排序的性能最优，其次为ODListsort排序，且二者的性能较为接近，而归并排序的性能最差；随着数据量的增加，3种排序算法的性能差异越来越明显。

在数据集已经有序的情况下，采用快速排序、归并排序和ODListsort排序算法进行排序，结果如表3所示。

表3 有序数据集下ODListsort排序与快速排序和归并排序的比较Table3 Comparison of ODListsort，quick sort and merge sort under the ordered data sets

由表3可见，对有序数据集进行排序时，ODListsort排序的性能最优，归并排序次之，而快速排序的性能最差，并且随着数据量的增加，3种排序算法的性能差异也越来越明显。

综上所述，从整体性能来看，ODListsort算法比归并排序更好，同时也不逊于快速排序。

4 结语

本文提出的ODListsort算法是基于元素以链表形式进行动态内存分配的比较排序算法。该算法的最好时间复杂度为O（n），最坏时间复杂度为O［n2／（4L）］，平均时间复杂度为O［nK／（L－1）］。对于随机数据集，ODListsort排序与快速排序的性能相当，比归并排序、选择排序、插入排序、冒泡排序的效率更高；对于有序数据集，由于排序过程中实际生成的链表数量K大为减少，致使ODListsort排序的效率远超快速排序，略高于归并排序。

但是，本文对于ODListsort算法在运行过程中允许共存的最大链表数量L并未得出确切的计算模型，而是给出的经验计算式。数据量n以及硬件设施性能都与L的取值相关，从而影响到ODListsort排序算法的效率，因此，如何针对不同的运行环境给出动态的L值计算模型还有待于深入研究。

［1］Hoare C A R.Algorithm 64：quicksort［J］.Communications of the ACM，1961，4（7）：321.

［2］Knuth D E.The art of computer programming，Volume 3：sorting and searching［M］.Boston：Addison－Wesley，1997：138－141.

［3］Lipschutz S.Theory and problems of data structures，Schaum’s outline series：international edition［M］.New York：McGraw－Hill，1986：324－325.

［4］白宇，郭显娥.单向链表快速排序算法［J］.计算机工程与科学，2014，36（1）：115－120.

［5］王善坤，陶祯蓉.一种三路划分快速排序的改进算法［J］.计算机应用研究，2012，29（7）：2513－2516.

［6］钟雪灵.基于动态规划的分批排序算法［J］.计算机工程与应用，2010，46（7）：229－231，235.

［7］Nardelli E，Proietti G.Efficient unbalanced mergesort［J］.Information Sciences，2006，176：1321－1337.