單向鏈表快速排序算法＊

白 宇，郭顯娥

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 大同037009）

1 引言

單向鏈表是一種典型的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)［1］，目前多使用 Two－way MergeSort算法［2］對(duì)單向鏈表進(jìn)行排序，雖然Two－way MergeSort算法時(shí)間復(fù)雜度為 O （n log2n）［1～4］，但 其 空 間 復(fù) 雜 度 高 達(dá)O（n）［1～4］，在一些嵌入式系統(tǒng)研發(fā)中，由于對(duì)存儲(chǔ)空間的使用數(shù)量有較嚴(yán)格的限制，故并不普遍適用。

排序算法中適應(yīng)性最強(qiáng)且應(yīng)用最廣的是基于關(guān)鍵字比較的排序算法［1～4］，因?yàn)榕判虻谋举|(zhì)就是按照一定規(guī)則相互比較關(guān)鍵字以確定其順序，即關(guān)鍵字可比較是排序算法的充要條件［3］。而其它諸如基于哈希表的排序算法或基于對(duì)關(guān)鍵字運(yùn)算的排序算法，由于對(duì)關(guān)鍵字有一些特殊要求，其應(yīng)用相對(duì)較窄［4～6］。

在基于關(guān)鍵字比較的排序算法中，已證明時(shí)間復(fù)雜度最小可達(dá)O（nlog2n）［4～6］，其中應(yīng)用最廣泛的有QuickSort和HeapSort，HeapSort算法的常量因子較高［5，6］，QuickSort算法的實(shí)測(cè)平均性能最優(yōu)［5，6］。但是，QuickSort算法最大不足之處在于，由于其基于可索引存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)（一般為數(shù)組或索引表），因而無法用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)［4］，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)際應(yīng)用非常廣泛，例如動(dòng)態(tài)存儲(chǔ)管理、動(dòng)態(tài)優(yōu)先級(jí)調(diào)度等等。本文針對(duì)上述問題，以QuickSort的分治策略［1～6］為基礎(chǔ)，提出一種可用于單向鏈表的QuickSort算法，其平均時(shí)間復(fù)雜度（包含最優(yōu)及最差情況）為O（nlog2n），輔助空間復(fù)雜度為O（0），平均遞歸?？臻g復(fù)雜度為O（log2n），從而實(shí)現(xiàn)了對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)高效排序的同時(shí)不增大空間復(fù)雜度。

2 算法分析

2.1 分治策略

QuickSort算法需要從線性表兩端逐一選取元素與樞軸元素進(jìn)行比較［1～6］，而單向鏈表只能從一個(gè)方向順序訪問，故無法做到；即使是雙向鏈表，QuickSort算法也要求可以任意交換兩個(gè)元素，單向或雙向鏈表也因不能隨機(jī)訪問而無法做到。因此，若要對(duì)單向鏈表實(shí)施分治策略，只能將單向鏈表的首節(jié)點(diǎn)作為樞軸節(jié)點(diǎn)，然后從單向鏈表首部的第二個(gè)節(jié)點(diǎn)開始，逐一遍歷所有后續(xù)節(jié)點(diǎn)，并將這些已遍歷節(jié)點(diǎn)的key與樞軸節(jié)點(diǎn)的key進(jìn)行比較，根據(jù)比較結(jié)果，重新將這些節(jié)點(diǎn)鏈接為兩個(gè)單向鏈表，其中之一所包含節(jié)點(diǎn)的key均小于樞軸節(jié)點(diǎn)的key；另一個(gè)所包含節(jié)點(diǎn)的key均大于或等于樞軸節(jié)點(diǎn)的key。這樣，便得到兩個(gè)規(guī)模更小的單向鏈表，然后對(duì)其遞歸執(zhí)行同樣的操作，并將其分別鏈接到樞軸節(jié)點(diǎn)的前部和后部。當(dāng)在某一層遞歸中，單向鏈表的節(jié)點(diǎn)數(shù)量小于或等于1時(shí)，則為遞歸出口。

為了能在每次劃分后將規(guī)模更小的兩個(gè)單向鏈表鏈接到樞軸節(jié)點(diǎn)上，必須記錄各自的尾節(jié)點(diǎn)位置，即需要設(shè)置兩個(gè)指向尾節(jié)點(diǎn)的指針。本文所述算法中將由key小于樞軸節(jié)點(diǎn)key構(gòu)成的單向鏈表定義為less；由key大于或等于樞軸節(jié)點(diǎn)key構(gòu)成的單向鏈表定義為more。這樣，less單向鏈表的首節(jié)點(diǎn)指針設(shè)定為lessHead，尾節(jié)點(diǎn)指針設(shè)定為lessTail；more單向鏈表的首節(jié)點(diǎn)指針設(shè)定為moreHead，尾節(jié)點(diǎn)指針設(shè)定為moreTail；當(dāng)前正在遍歷的節(jié)點(diǎn)指針設(shè)定為current；由于樞軸節(jié)點(diǎn)就是未排序的單向鏈表的首節(jié)點(diǎn)，故樞軸節(jié)點(diǎn)指針設(shè)定為listHead。

設(shè)節(jié)點(diǎn)包含兩個(gè)域：key表示用于比較的關(guān)鍵字（圖中的k1，k2，…，kn等），next表示指向下一節(jié)點(diǎn)的指針（圖中節(jié)點(diǎn)的空白區(qū)域）。初始化狀態(tài)如圖1所示，此時(shí)current為listHead的next域。

Figure 1 Initializaton state圖1 初始化狀態(tài)

當(dāng)遍歷單向鏈表的兩個(gè)節(jié)點(diǎn)后，狀態(tài)如圖2所示，設(shè)k2＜k1，k3≥k1。

Figure 2 State of traversing two nodes圖2 遍歷兩個(gè)節(jié)點(diǎn)后的狀態(tài)

當(dāng)繼續(xù)遍歷單向鏈表的k4和k5節(jié)點(diǎn)后，狀態(tài)如圖3所示，設(shè)k4＜k1，k5≥k1。

Figure 3 State of traversing four nodes圖3 遍歷四個(gè)節(jié)點(diǎn)后的狀態(tài)

當(dāng)單向鏈表遍歷結(jié)束后，與可索引表的QuickSort算法相類似［1～6］，亦即完成了一趟劃分，如此遞歸進(jìn)行，便可完成整個(gè)單向鏈表的排序。之所以需要設(shè)定兩個(gè)指向單向鏈表尾節(jié)點(diǎn)的指針lessTail和moreTail，一是如前文所述，簡(jiǎn)化將less和more單向鏈表鏈接到樞軸節(jié)點(diǎn)前、后部的過程；二是簡(jiǎn)化向less和more單向鏈表中添加節(jié)點(diǎn)的過程，否則需逐一遍歷節(jié)點(diǎn)，以尋找該單向鏈表的尾節(jié)點(diǎn)，將耗費(fèi)時(shí)間復(fù)雜度為O（n）的操作。

2.2 算法正確性分析

算法正確性需要從兩個(gè)方面進(jìn)行分析，其一，當(dāng)以樞軸節(jié)點(diǎn)為中心進(jìn)行一趟劃分后，樞軸節(jié)點(diǎn)前后兩個(gè)單向鏈表中節(jié)點(diǎn)的key是否相對(duì)于樞軸節(jié)點(diǎn)有序；其二，遞歸過程是否一定有出口，即遞歸過程是否一定可以在有限步驟后結(jié)束。

針對(duì)第一個(gè)問題，通過遍歷并重新鏈接原單向鏈表為兩個(gè)新的子單向鏈表進(jìn)行解決。在一趟劃分過程中，從樞軸節(jié)點(diǎn)listHead的下一個(gè)節(jié)點(diǎn)開始依次遍歷單向鏈表中的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)的key小于樞軸節(jié)點(diǎn)listHead的key，則將該節(jié)點(diǎn)鏈接到新的子單向鏈表lessHead中；否則將該節(jié)點(diǎn)鏈接到新的子單向鏈表moreHead中。當(dāng)遍歷結(jié)束時(shí)，所得的子單向鏈表lessHead中的所有節(jié)點(diǎn)的key一定小于樞軸節(jié)點(diǎn)listHead的key。不失一般性，如圖3，設(shè)節(jié)點(diǎn)k2＜k1，k4＜k1，則由k2，k4…構(gòu)成的子單向鏈表lessHead中的所有節(jié)點(diǎn)的key均小于樞軸節(jié)點(diǎn)listHead的key；同理，由k3，k5…構(gòu)成的子單向鏈表moreHead中的所有節(jié)點(diǎn)的key均大于或等于樞軸節(jié)點(diǎn)listHead的key。根據(jù)2.1節(jié)的描述，此時(shí)將樞軸節(jié)點(diǎn)listHead鏈接到lessTail后，再將moreHead鏈接到listHead后，不失一般性，如圖3，樞軸節(jié)點(diǎn)k1成為兩個(gè)子單向鏈表的分割點(diǎn)。因此，以樞軸節(jié)點(diǎn)為中心進(jìn)行一趟劃分后，樞軸節(jié)點(diǎn)前后兩個(gè)單向鏈表中節(jié)點(diǎn)的key相對(duì)于樞軸節(jié)點(diǎn)是有序的。

針對(duì)第二個(gè)問題，通過劃分后所形成的兩個(gè)子單向鏈表的規(guī)模不斷減小，并且當(dāng)子單向鏈表節(jié)點(diǎn)數(shù)量小于或等于1時(shí)通過終止遞歸調(diào)用來解決。一趟劃分后無論劃分結(jié)果如何，樞軸節(jié)點(diǎn)的位置已經(jīng)固定，即到達(dá)了樞軸節(jié)點(diǎn)在排序后所應(yīng)處于的最終位置上，因此，樞軸節(jié)點(diǎn)將不再參與下一輪遞歸調(diào)用的劃分過程。因此，在一趟劃分后對(duì)兩個(gè)子單向鏈表遞歸調(diào)用劃分算法時(shí)，其規(guī)模（節(jié)點(diǎn)數(shù)量）總是在不斷減小的。當(dāng)在某一層遞歸調(diào)用劃分算法時(shí)，如果lessHead等于null，或lessHead等于lessTail，則說明該子單向鏈表中的節(jié)點(diǎn)數(shù)量小于或等于1，顯然，可以認(rèn)為該子單向鏈表已經(jīng)有序，故而可以終止遞歸調(diào)用；同理，如果moreHead等于null，或moreHead等于moreTail，同樣可以終止遞歸調(diào)用，即此時(shí)便是遞歸出口。

通過上述兩個(gè)方法，可以保證本文所述算法的正確性。

2.3 算法復(fù)雜度

2.3.1 時(shí)間復(fù)雜度

通過2.1節(jié)的分析容易得出，一趟劃分后，樞軸節(jié)點(diǎn)對(duì)less和more單向鏈表的最優(yōu)情況是均分（即節(jié)點(diǎn)數(shù)量之差不大于1）；最差情況是其中之一為空；平均而言，樞軸節(jié)點(diǎn)可能出現(xiàn)在1到n的某個(gè)位置，顯然包括最優(yōu)及最差情況。現(xiàn)就三種情況分別分析如下：

第一種情況，每次劃分都將less和more單向鏈表均分，則遞歸棧深度為 log2n＋1，即需遞歸log2n次［7，8］，設(shè)需要時(shí)間T（n）。第一次劃分需對(duì)key做n次比較；第二次劃分，兩個(gè)單向鏈表各自需要時(shí)間T（n/2）；然后不斷劃分，可得不等式推斷如式（1）：

由式（1）可知，本文所述算法在最優(yōu)情況下的時(shí)間復(fù)雜度為O（nlog2n）。

第二種情況，每次劃分后，less或more單向鏈表中有且僅有一個(gè)為空，則共需進(jìn)行n－1次劃分，可得：

由式（2）可知，本文所述算法在最差情況下的時(shí)間復(fù)雜度為O（n2）。

第三種情況，平均而言，設(shè)樞軸節(jié)點(diǎn)在劃分后處于第k個(gè)位置（1≤k≤n），可得：

式（3）等價(jià)：

式（4）兩邊同乘n，得：

式（5）整理得：

式（6）兩邊同時(shí)除以n（n＋1），得：

將式（7）中的等式相加，并使用公式：

式（8）中γ≈0.5772，即歐拉常數(shù)，可得：

由式（9）可知，本文所述算法在平均情況下（包含最優(yōu)及最差情況），時(shí)間復(fù)雜度為O（nlog2n），且遞歸棧平均深度為Θlog2n（Θ為常數(shù)）。

2.3.2 空間復(fù)雜度

由于本文所述算法采用遞歸結(jié)構(gòu)，因此空間復(fù)雜度需從兩個(gè)方面進(jìn)行分析：

（1）用于排序的輔助空間。從2.1節(jié)的分析可知，由于算法在排序過程中僅僅重新鏈接原單向鏈表的節(jié)點(diǎn)，并不需要任何輔助空間存儲(chǔ)節(jié)點(diǎn)。完全不同于針對(duì)可索引存儲(chǔ)結(jié)構(gòu)的排序算法，需要輔助空間進(jìn)行元素交換［1～5］。因此，輔助空間復(fù)雜度為O（0）。

（2）遞歸?？臻g。從2.3.1節(jié)的分析可知，算法的遞歸棧平均深度為Θlog2n（Θ為常數(shù)），因此平均遞歸?？臻g復(fù)雜度為O（log2n）。

3 算法描述

單向鏈表快速排序算法描述如下，具體實(shí)現(xiàn)代碼不再贅述：

步驟1 算法接收兩個(gè)指針，其中l(wèi)istHead指向單向鏈表首節(jié)點(diǎn)，listTail為空指針，劃分過程中，listTail將指向單向鏈表的尾節(jié)點(diǎn)，劃分后用于鏈接less單向鏈表到樞軸節(jié)點(diǎn)前。

步驟2 如果單向鏈表listHead僅有一個(gè)節(jié)點(diǎn)，則說明已有序，本層遞歸結(jié)束，返回listHead。

步驟3 令lessHead、lessTail、moreHead和moreTail為空，令current為listHead的next域，即單向鏈表的第二個(gè)節(jié)點(diǎn)。

步驟4 如果current節(jié)點(diǎn)為空，則轉(zhuǎn)入步驟13。

步驟5 如果current節(jié)點(diǎn)的key小于樞軸節(jié)點(diǎn)（即listHead）的key，則current節(jié)點(diǎn)應(yīng)鏈接到less單向鏈表，轉(zhuǎn)入步驟6；否則，current節(jié)點(diǎn)應(yīng)鏈接到more單向鏈表，轉(zhuǎn)入步驟9。

步驟6 修改lessTail指針使其指向current節(jié)點(diǎn)。如果lessHead為空，則轉(zhuǎn)入步驟7；否則轉(zhuǎn)入步驟8。

步驟7 將current節(jié)點(diǎn)鏈接為less單向鏈表的首節(jié)點(diǎn)。

步驟8 將current節(jié)點(diǎn)鏈接為less單向鏈表的尾節(jié)點(diǎn)。

步驟9 修改moreTail指針使其指向current節(jié)點(diǎn)。如果moreHead為空，則轉(zhuǎn)入步驟10；否則轉(zhuǎn)入步驟11。

步驟10 將currnet節(jié)點(diǎn)鏈接為more單向鏈表的首節(jié)點(diǎn)。

步驟11 將currnet節(jié)點(diǎn)鏈接為more單向鏈表的尾節(jié)點(diǎn)。

步驟12 將current節(jié)點(diǎn)移動(dòng)到單向鏈表的下一個(gè)節(jié)點(diǎn)。

步驟13 如果more單向鏈表不為空，則轉(zhuǎn)入步驟14；否則轉(zhuǎn)入步驟18。

步驟14 標(biāo)記more單向鏈表的結(jié)束位置，即置moreTail的next域?yàn)榭铡?/p>

步驟15 遞歸調(diào)用本算法，繼續(xù)劃分more單向鏈表，傳入moreHead和moreTail。

步驟16 將經(jīng)過遞歸排序的more單向鏈表鏈接到樞軸節(jié)點(diǎn)后。

步驟17 修改listTail指針使其指向more－Tail，以便本層遞歸結(jié)束后供上層遞歸過程使用。

步驟18 由于more單向鏈表為空，則樞軸節(jié)點(diǎn)便是尾節(jié)點(diǎn)，即置listHead的next域?yàn)榭铡?/p>

步驟19 修改listTail指針使其指向listHead。

步驟20 如果less單向鏈表不為空，則轉(zhuǎn)入步驟21；否則轉(zhuǎn)入步驟24。

步驟21 標(biāo)記less單向鏈表的結(jié)束位置，即置lessTail的next域?yàn)榭铡?/p>

步驟22 遞歸調(diào)用本算法，繼續(xù)劃分less單向鏈表，傳入lessHead和lessTail。

步驟23 將經(jīng)過遞歸排序的less單向鏈表鏈接到樞軸節(jié)點(diǎn)前。

步驟24 由于less單向鏈表為空，則樞軸節(jié)點(diǎn)便是首節(jié)點(diǎn)，即置lessHead為listHead。

步驟25 本層遞歸結(jié)束，返回lessHead。

4 實(shí)驗(yàn)測(cè)試

4.1 與單向鏈表排序算法實(shí)測(cè)比較

當(dāng)前廣泛用于單向鏈表且時(shí)間復(fù)雜度為O（nlog2n）的排序算法僅有 Two－way MergeSort一種［5］，因此在實(shí)驗(yàn)測(cè)試中，選擇該算法作橫向比較，無序數(shù)據(jù)量分別取25 k、50 k、75 k、100 k和500 k，數(shù)據(jù)呈均勻隨機(jī)分布，范圍為［0，數(shù)據(jù)量＊2）的正整數(shù)［9～12］。使用 C＃2010編譯，在Intel i5 750（2.66 GHz）上運(yùn)行。取5個(gè)不同的隨機(jī)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集測(cè)試10次，計(jì)算算術(shù)平均值，結(jié)果如表1所示。

Table 1 Test data 1表1 實(shí)測(cè)數(shù)據(jù)一

由表1可知，針對(duì)單向鏈表排序，本文所述算法比Two－way MergeSort算法效率平均提升約26.85%。

4.2 與線性表QuickSort算法實(shí)測(cè)比較

由于線性表QuickSort算法樞軸節(jié)點(diǎn)的選取有多種方式［4～6］，為了避免由于樞軸節(jié)點(diǎn)選取的不同而導(dǎo)致排序效率的差異［4～6］，需要一致的比較基礎(chǔ)，故本文選擇了使用首節(jié)點(diǎn)作為樞軸節(jié)點(diǎn)的線性表QuickSort算法作為對(duì)比算法，測(cè)試數(shù)據(jù)量、分布、范圍以及測(cè)試方法均與4.1節(jié)相同，結(jié)果如表2所示。

Table 2 Test data 2表2 實(shí)測(cè)數(shù)據(jù)二

由表2可知，針對(duì)相同數(shù)據(jù)，本文所述算法比基于線性表的QuickSort算法效率平均提升約11.38%。

5 結(jié)束語

綜上所述，本文所述算法的平均時(shí)間復(fù)雜度（包含最優(yōu)及最差情況）為O（nlog2n），已達(dá)到基于比較的排序算法的時(shí)間復(fù)雜度的理論極限；其輔助空間復(fù)雜度為O（0），即無任何輔助空間開銷；平均遞歸?？臻g復(fù)雜度為O（log2n），達(dá)到了除尾遞歸［7～8，13，14］以外的最小遞歸?？臻g復(fù)雜 度。因此，本文所述算法的優(yōu)勢(shì)是高效率、低開銷，各項(xiàng)指標(biāo)較為均衡，是當(dāng)前時(shí)間復(fù)雜度等于或接近O（nlog2n）排序算法中為數(shù)不多的可應(yīng)用于單向鏈表的排序算法之一。不足之處是由于單向鏈表不可索引，故劃分算法中不能像基于線性表的QuickSort算法那樣選取中值節(jié)點(diǎn)［4～6］作為樞軸節(jié)點(diǎn)。根據(jù)文獻(xiàn)［5］的實(shí)驗(yàn)結(jié)果，基于線性表的QuickSort算法使用中值節(jié)點(diǎn)作為樞軸節(jié)點(diǎn)后，在均勻和高斯隨機(jī)數(shù)據(jù)分布狀態(tài)下，實(shí)測(cè)有2%～4%的效率提升。

［1］ Joseph B.Data structure programming［M］.New York：Springer Verlag，2005.

［2］ Main M，Savitch W.Data structure and other objects using C＋＋［M］.Boston：Addison－Wesley，2004.

［3］ Kleinberg J，Tardos E.Algorithm design［M］.Boston：Addison－Wesley，2005.

［4］ Thomas H C，Charles E L，Roonald L R，et al.Introduction to algorithms［M］.Massachusetts：Mit Pr，2005.

［5］ Sedgewick R，Wayne K.Algorithms［M］.4th edition.New Jersey：Pearson Education，2012.

［6］ Hagerup T.Algorithm theory—Swat 2004［M］.New York：Springer Verlag，2004.

［7］ Cai Jing－qiu.Note of on recursive program transformation［J］.Microelectronics ＆ Computer，1995，12（6）：45－46.（in Chinese）

［8］ Davies J，Schneider S.Recursion induction for real－time processe［J］.Formal Aspects of Computing.2010，19（2）：119－127.

［9］ Wang Xin－cheng，Sun Hong.Research＆design on high－performance pseudo－random number generator［J］.Computer Engineering and Applications，2004，40（11）：20－23.（in Chinese）

［10］ Qian Hong－bing.The automatic generation of test data［J］.Computer Engineering，1996，22（2）：13－14.（in Chinese）

［11］ Ye Shao－kang，Li Zheng.True random number generator based on mixed－signal circuit［J］.Computer Engineering and Design，2012，33（4）：1602－1606.（in Chinese）

［12］ Ma Xin－sheng，Hu Bin.Research on derivative estimation of periodic random data with hidden periodical model［J］.Journal of Nanchang University（Engineering ＆ Technology），2011，33（2）：200－204.（in Chinese）

［13］ Pitts A M.Structural recursion with locally scoped names［J］.Journal of Functional Programming，2011，21（3）：235－286.

［14］ Jaime A，Bohórquez V.An elementary and unified approach to program correctness［J］.Formal Aspects of Computing，2010，7（9）：38－43.

附中文參考文獻(xiàn)：

［7］ 蔡經(jīng)球.關(guān)于遞歸程序變換的注記［J］.微電子學(xué)與計(jì)算機(jī)，1995，12（6）：45－46.

［9］ 王新成，孫宏.高速偽隨機(jī)數(shù)發(fā)生器的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（11）：20－23.

［10］ 錢紅兵.測(cè)試數(shù)據(jù)的自動(dòng)生成［J］.計(jì)算機(jī)工程，1996，22（2）：13－14.

［11］ 葉少康，李崢.基于數(shù)?；旌系恼骐S機(jī)數(shù)發(fā)生器［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（4）：1602－1606.

［12］ 馬新生，胡斌.潛周期模型在周期性隨機(jī)數(shù)據(jù)的數(shù)值微分中的應(yīng)用研究［J］.南昌大學(xué)學(xué)報(bào)（工科版），2011，33（2）：200－204.