链式归并排序法

摘要：介绍一种链式存储的逐步归并排序算法，其最佳时间复杂度为O(n)，空间复杂度为O(1)。

关键词：链表；归并排序；算法；复杂性

0　引言

排序问题是指给定一个数据项集，使其中的数据按递增或递减排列。数据项可以是具有线性顺序的任意对象。排序是计算机科学中最重要的研究课题之一，据统计，在大型计算中心，排序工作往往要占去大约1/4的计算时间。排序具有极高的理论和实际价值，2000年被列为对科学和工程计算的研究与实践影响最大的十大问题之一。对排序算法的研究无论是在理论上还是在实践上都具有重大的意义。

数十年来，人们在此问题上进行了不懈的研究，获得了大量的研究成果，各种排序方法有近百种之多。这其中最常用的就有：快速排序、希尔排序、冒泡排序、插入排序、选择排序、堆排序、归并排序、基数排序、杂凑排序等十多种排序算法。这些排序算法基本上可以归为两大类：基于比较的排序和不基于比较的排序。基于比较的排序是指要将各个数据项进行直接或间接的比较以确定每个数据的最终位置。理论研究表明，不基于比较的排序如基数排序、杂凑排序的时间复杂度可以达到O(n)，但问题是这类排序一般都需要较大的辅助空间，而且对数据项有着比较严格的要求，只能在特性场合下使用。基于比较的排序的时间下限是O(nlog2n)，快速排序、堆排序、归并排序的平均时间复杂度都可以达到这个级别。这类排序对数据项没有任何限制，因而获得了更为广泛的应用。本文是在数据的链式存储的基础上对数据进行排序方法的探讨，从逐渐合并有序链来达到排序的目的。

1　算法的基本思路

我们知道归并排序是将序列分成基本均匀的两部分，对两部分都需排序之后再合并。该算法的优点是无论原序列的分布情况如何，它的划分总是均匀的，因此最好情况和最坏情况的时间复杂度都是O(nlog2n)，空间复杂度为O(n)。它采用的是顺序存储，算法用递归的方式实现。如果我们用非顺序的方式，用不等长的非递归方式实现可以得到性能更好的归并排序算法。

1.1链式归并排序算法的基本思想

首先根据原始数据的顺序建立一条单链表，将在无序链中以表首结点为首结点寻找一条新的有序链，将其归并到原来的有序链中，再在剩下的无序链中以表首结点为首结点寻找一条有序链，再归并……直到所有结点都归并到有序链中去为止。

1.2具体算法描述

Step 1：输入n个待排数据，用插入法建立一条单链表为原链表link；将原有序链lastorderlink和新有序链neworderlink都初始化为空链表；

Step 2：将工作指针p指向原链表link表的新的表首结点；

Step 3：如果p为空，转step 8，否则继续进行；

Step 4：将原链表link表的表首结点(p所指结点)取出(p指针需下移一位)作为新有序表neworderlink的表首结点插入；

Step 5：如果p为非空，则继续Setp 6，否则转step7；

Setp 6：如果p所指结点的值不小于新有序表neworderlink的表尾结点值就从rink表中取出并将其插入到neworderfink表的链尾，p指针下移，否则p指针仅下移，转Step 5；

Setp 7：将新有序表neworderlink归并到原有序链las-torderlink中，并将新有序链neworderlink置为空表，转Step 2；

Setp 8：排序结束，lastorderlink中即为有序链表。

1.3算法示例

示例如下：原始数据为：32、59、21、12、45、89、63、34、26、11、7、6、18、24、29、64、3、46、77、22。以头插入的方式建立单链表。

具体排序过程见图1～图5所示：

1.4算法流程图

算法流程图如图6所示。

2　算法分析

2.1时间复杂度

(1)当原始待排数据为正序有序时，只需进行一趟就结束，时间复杂度为O(n)(最好情况)；

(2)当原始待排数据为逆序有序时，每一趟新有序链表中只有一个结点，需进行n-1趟，蜕化到选择排序，其时间复杂度即为O(n2)(最坏情况，有待改进)；

(3)当原始待排数据为随机分布时，时间复杂度为O(nlogn)；

(4)当原始待排数据为所有值相同时，只需进行一趟就结束，时间复杂度为O(n)；

(5)当原始待排数据为波形分布(假定波长为C)时，时间复杂度为O(Cn)；

(6)当原始待排数据为峰型分布(先正序后逆序)和谷型分布(先逆序后正序)时，时间复杂度为最坏情况的一半。

2.2空间复杂性

需要几个辅助的工作指针，空间复杂度为O(1)。

3　结束语

从上面的分析可以看出，本算法除了在随机分布数据的排序上的效率略接近于传统的二路归并外，最佳情况好于后者，可见改进是成功的。当然本算法还有很多值得改进的地方。例如，当逆序或峰型谷型分布时，有待于改进。