一種基于有序雙端鏈表的高效排序算法

譚 林，廖光忠

（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.