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

譚 林，廖光忠

（1.武漢科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北 武漢，430065；2.武漢科技大學(xué)智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，湖北 武漢，430065）

排序是計算機程序設(shè)計中的一項重要操作，它的功能是將亂序的數(shù)據(jù)元素按照一定的順序重新排列以減少每次數(shù)據(jù)訪問所消耗的時間和資源。排序算法可分為比較排序算法和非比較排序算法。在非比較排序算法中，由于數(shù)據(jù)元素的關(guān)鍵字本身就含有了定位特征，因而不需要比較就可以確定其前后位置。適應(yīng)性更強、應(yīng)用更廣的比較排序算法則是通過對一個抽象內(nèi)容的比較操作來確定兩個數(shù)據(jù)元素的前后順序，該算法的唯一要求就是操作數(shù)滿足全序關(guān)系。比較排序算法中，在最好情況下的時間復(fù)雜度為O（n），在最壞情況下的時間復(fù)雜度為O（n2），其中效率比較高的算法有快速排序、歸并排序和堆排序，它們的平均時間復(fù)雜度均為O（nlog2n）［1－3］。

本文提出一種新的基于有序雙端鏈表的排序算法，即 ODListsort（ordered double－end linked list sort）算法。該算法是基于元素以鏈表形式進行動態(tài)內(nèi)存分配的比較排序算法，主要由計算鏈表最大數(shù)量、插入操作和合并鏈表3個部分組成。本文首先介紹ODListsort排序算法的操作流程，然后分析其時間復(fù)雜度，最后通過數(shù)據(jù)測試實驗對該算法和幾種經(jīng)典排序算法的性能進行比較。

1 ODListsort算法

ODListsort算法具體包含3個部分，分別是計算鏈表的最大數(shù)量、鏈表的雙端插入操作以及相鄰鏈表的合并操作。整個排序過程就是將元素按照一定規(guī)則插入到鏈表中，然后合并這些鏈表，如此反復(fù)地插入、合并直至生成一個包含所有元素的有序鏈表。

1.1 計算鏈表最大數(shù)量

鏈表的數(shù)量會隨著數(shù)據(jù)范圍的不同而改變，為了降低算法的時間復(fù)雜度，這里首先定義一個可共存的鏈表最大數(shù)量L，當現(xiàn)存鏈表數(shù)量達到L時就要執(zhí)行鏈表的合并操作，這樣做的好處是，使合并過程中的鏈表節(jié)點數(shù)差距不大從而減少比較次數(shù)。

L通過create（）函數(shù)計算。將需要進行排序的元素數(shù)量n傳遞給create（）函數(shù)，函數(shù)返回計算出的L值。create（）函數(shù)的偽代碼如下，其中t為自定義變量，其取值是根據(jù)實驗反復(fù)測試得到的。

1.2 插入操作

一般情況下，插入操作會打亂先前已排好序的數(shù)據(jù)，所以每次插入元素之后都必須進行一次重排序，增加了許多重復(fù)操作，消耗大量時間［4］。因此，在ODListsort算法中加入了插入規(guī)則，使得每次插入操作后均保持原鏈表有序。此時的鏈表就像一個雙端數(shù)列，數(shù)據(jù)可以從兩端插入［5］。插入操作和鏈表的生成過程是同時進行的。

具體插入規(guī)則為：將要插入的元素與鏈表中第一個和最后一個元素進行比較，如果插入元素比鏈表第一個元素更小，則該元素插入到鏈表第一個元素的前面；如果插入元素比鏈表最后一個元素更大，則該元素插入到鏈表最后一個元素的后面；否則，建立一個新的空鏈表，并將該元素插入到新建鏈表里面。因為每次插入都會與鏈表第一個和最后一個元素進行比較，所以即使插入了新的元素也可以保持原鏈表有序，無需對鏈表重新排序。

下面以一個包含10個元素的數(shù)據(jù)集｛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的尾部；④重復(fù)插入元素25、99；⑤插入元素1，因為99＞1＞0，根據(jù)插入規(guī)則需要另外新建一個空鏈表list 2并插入元素1，這樣就建立了兩個鏈表；⑥繼續(xù)插入操作到元素15的時候，又出現(xiàn)與元素1相同的情況，再次建立一個空鏈表list 3并插入15；⑦插入元素19。最后完成插入操作后總共生成了3個鏈表，如圖1所示。從圖1中可以看到，這3個鏈表都是有序的，所有鏈表的第一個元素均按照升序排列，所有鏈表的最后一個元素均按照降序排列。

插入函數(shù)list＿insert（）的偽代碼為：

圖1 生成的鏈表Fig.1 The generated lists

1.3 合并鏈表

當數(shù)據(jù)插入完成后進行合并操作，合并時以遞歸的方式將所有鏈表合并成一個［6］。最后一個鏈表命名為final＿list，將final＿list與其前一個鏈表previous＿list進行合并形成新的final＿list，如此反復(fù)直到所有的鏈表都合并成一個final＿list。以下是合并函數(shù)list＿merge（）的偽代碼。

2 ODListsort算法的時間復(fù)雜度

排序算法的性能指標有時間復(fù)雜度和空間復(fù)雜度，隨著計算機硬件的升級，內(nèi)存資源變得越來越豐富，排序算法的空間復(fù)雜度已經(jīng)不是一個太大的問題［7］。因此，本文重點對ODListsort算法的時間復(fù)雜度進行計算分析。

2.1 最好時間復(fù)雜度

當有n個元素的數(shù)據(jù)集已經(jīng)按照升序或者降序排列好的時侯，ODListsort算法具有最好時間復(fù)雜度。因為此時ODListsort算法只需要進行插入操作，只會新建一個鏈表，不需要后續(xù)的合并操作，故該算法的最好時間復(fù)雜度為O（n）。很明顯，在這種情況下，ODListsort算法要優(yōu)于快速排序和歸并排序算法。最好時間復(fù)雜度Tb的計算公式為：

2.2 平均時間復(fù)雜度

ODListsort算法的平均時間復(fù)雜度計算是建立在隨機數(shù)據(jù)集上的。假設(shè)數(shù)據(jù)量為n，實際排序過程中生成的鏈表總量為K，可共存鏈表的最大數(shù)量為L，通常情況下，n?K?L。例如，對于一個有100000個隨機數(shù)的數(shù)據(jù)集，通過實驗可以發(fā)現(xiàn)，K值約為2000，L值為50～85。

用Ta表示平均時間復(fù)雜度。在一次完整的插入過程（即生成L個鏈表）中，所需要的比較次數(shù)為：

因為生成L個鏈表的次數(shù)總共為K／L次，所以插入比較的總次數(shù)為：

因此，對于整個插入操作，時間復(fù)雜度為O（KL）。

對于合并操作，在平均情況下，n個元素被插入到K 個鏈表中，即每個鏈表有n／K個元素，對于L個鏈表的一次合并過程所需要的比較次數(shù)為：

因為在對L個鏈表進行第一次合并之后，再生成L－1個鏈表才進行第二次合并，所以總共需要的合并次數(shù)為K／（L－1），那么合并操作的總比較次數(shù)為：

因此，合并操作的時間復(fù)雜度為O［nK／（L－1）］。

因為插入操作的時間復(fù)雜度為O（KL），與n無關(guān)，且遠小于合并操作的時間復(fù)雜度，因此ODListsort算法的平均時間復(fù)雜度就為合并操作的時間復(fù)雜度O［nK／（L－1）］。

2.3 最壞時間復(fù)雜度

首先舉例說明一種極端情況，當出現(xiàn)類似｛0，9，1，8，2，7，3，6，4，5｝的最壞數(shù)據(jù)集的時候，一次插入過程會生成5個鏈表，其中每個鏈表僅包含2個元素。對于有n個元素的數(shù)據(jù)集，一次插入過程最多生成L個鏈表，一次合并過程要合并L個鏈表，如果實際運算過程中生成的鏈表總數(shù)為K，則插入操作和合并操作的總次數(shù)均為K／L，但在最壞的情況下，每個鏈表僅僅包含2個元素，故K＝n／2，因此插入操作和合并操作的總次數(shù)均為n／（2L）。

用Tw表示ODListsort算法的最壞時間復(fù)雜度。在最壞的情況下，一次插入過程中的比較次數(shù)為：

因此，對于整個插入操作，時間復(fù)雜度為O（nL）。

從最后一個鏈表到第二個鏈表的合并過程中的比較次數(shù)為：

n／（2L）次合并過程中，每一次合并L個鏈表的比較次數(shù)均為Tw（merge’）加上最后合并第一個鏈表的比較次數(shù)。

第1次合并L個鏈表的時候，因為第一個鏈表只包含2個元素，鏈表頭尾本來就是有序的，不需要再比較兩個鏈表的第一個元素和最后一個元素，所以比較次數(shù)為1，則第一次合并的比較次數(shù)為：

在第2次合并L個鏈表的過程中，首先合并含有2個元素的L－1個鏈表需要比較L（L－1）次，然后將合并后的L－1個鏈表與第一次合并L個鏈表得到的鏈表進行合并，比較次數(shù)為兩個鏈表的元素和，總的比較次數(shù)為：

故合并操作的時間復(fù)雜度為O［n2／（4L）］。

由于插入操作的時間復(fù)雜度O（nL）遠小于合并操作的時間復(fù)雜度O［n2／（4L）］，所以 ODListsort算法的最壞時間復(fù)雜度為O［n2／（4L）］。

3 排序?qū)嶒炁c結(jié)果分析

本實驗采用的硬件平臺為Pentium（R）Dual－Core E54002.70GHz，2G 內(nèi)存，軟件平臺為Windows 7操作系統(tǒng)，Dev C＋＋5.0集成開發(fā)環(huán)境，數(shù)據(jù)由隨機數(shù)生成器產(chǎn)生。

采用插入排序、選擇排序、冒泡排序和ODListsort排序算法對包含5×103～105個隨機數(shù)的數(shù)據(jù)集進行排序，結(jié)果如表1所示。

表1 ODListsort排序與插入排序、選擇排序和冒泡排序的比較Table1 Comparison of ODListsort，insertion，selection sort and bubble sort

由表1可見，ODListsort排序算法所消耗的時間比其他3種排序算法所消耗的時間少很多，而且數(shù)據(jù)量越大，這種時間差距越大。

采用快速排序、歸并排序和ODListsort排序算法對包含104～4×105個隨機數(shù)的數(shù)據(jù)集進行排序，結(jié)果如表2所示。

表2 ODListsort排序與快速排序和歸并排序的比較Table2 Comparison of ODListsort，quick sort and merge sort

由表2可見，當數(shù)據(jù)量為104～105時，3種排序算法的性能非常接近；當數(shù)據(jù)量為2×105～4×105時，快速排序的性能最優(yōu)，其次為ODListsort排序，且二者的性能較為接近，而歸并排序的性能最差；隨著數(shù)據(jù)量的增加，3種排序算法的性能差異越來越明顯。

在數(shù)據(jù)集已經(jīng)有序的情況下，采用快速排序、歸并排序和ODListsort排序算法進行排序，結(jié)果如表3所示。

表3 有序數(shù)據(jù)集下ODListsort排序與快速排序和歸并排序的比較Table3 Comparison of ODListsort，quick sort and merge sort under the ordered data sets

由表3可見，對有序數(shù)據(jù)集進行排序時，ODListsort排序的性能最優(yōu)，歸并排序次之，而快速排序的性能最差，并且隨著數(shù)據(jù)量的增加，3種排序算法的性能差異也越來越明顯。

綜上所述，從整體性能來看，ODListsort算法比歸并排序更好，同時也不遜于快速排序。

4 結(jié)語

本文提出的ODListsort算法是基于元素以鏈表形式進行動態(tài)內(nèi)存分配的比較排序算法。該算法的最好時間復(fù)雜度為O（n），最壞時間復(fù)雜度為O［n2／（4L）］，平均時間復(fù)雜度為O［nK／（L－1）］。對于隨機數(shù)據(jù)集，ODListsort排序與快速排序的性能相當，比歸并排序、選擇排序、插入排序、冒泡排序的效率更高；對于有序數(shù)據(jù)集，由于排序過程中實際生成的鏈表數(shù)量K大為減少，致使ODListsort排序的效率遠超快速排序，略高于歸并排序。

但是，本文對于ODListsort算法在運行過程中允許共存的最大鏈表數(shù)量L并未得出確切的計算模型，而是給出的經(jīng)驗計算式。數(shù)據(jù)量n以及硬件設(shè)施性能都與L的取值相關(guān)，從而影響到ODListsort排序算法的效率，因此，如何針對不同的運行環(huán)境給出動態(tài)的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］.計算機工程與科學(xué)，2014，36（1）：115－120.

［5］王善坤，陶禎蓉.一種三路劃分快速排序的改進算法［J］.計算機應(yīng)用研究，2012，29（7）：2513－2516.

［6］鐘雪靈.基于動態(tài)規(guī)劃的分批排序算法［J］.計算機工程與應(yīng)用，2010，46（7）：229－231，235.

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