陳根方，張立印

(杭州師范大學(xué) 信息科學(xué)與工程學(xué)院,浙江 杭州 310036)

(T1)p-1-(T2)p-1≥0

(T1)p+1-(T2)p+1≤0

0 前 言

排序算法是最常見的計算機(jī)算法之一，在大型計算機(jī)中，排序占用了CPU大約25%的運(yùn)行時間.排序的對象是有限集合或無序序列中的元素，排序是按某種規(guī)則將其重新進(jìn)行排列，最常用的規(guī)則是元素某個關(guān)鍵字的大小關(guān)系，排序后的序列元素之間的前后位置關(guān)系符合這種規(guī)則.

用來解決排序問題的算法多達(dá)幾十種，如表1所示為常見的排序算法[1].常用的衡量排序算法優(yōu)劣的因素是：時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性和適合場合.其中最主要的衡量因素是時間復(fù)雜度，常見的簡單排序算法有插入排序、冒泡排序、選擇排序[2]等，它們的平均時間復(fù)雜度都是O(n2)；而時間復(fù)雜度是O(nlogn)的常見排序算法有堆排序、合并排序和快速排序[2]；這6種排序算法都是基于比較的排序算法，也就是說在排序過程中，需要進(jìn)行大量的關(guān)鍵字值之間的大小比較，其中平均時間穩(wěn)定性較好的排序算法是快速排序算法.還有一些時間復(fù)雜度是O(n)的排序算法也被逐步發(fā)現(xiàn)，比如計數(shù)排序[3]、基數(shù)排序[4]、桶排序[5]、Flash sort[6],分段快速排序[7]、二次分“檔”鏈接排序方法[8]等等.

表1 常見的排序算法

不同的算法適用于不同的場合，有的算法適用于在外存中排序，如合并排序算法；有的算法適用于內(nèi)存中排序，如快速排序算法；有的適用于并行計算，有的適用于串行計算，有的適用于時空交換技術(shù)，有的適用于大容量的數(shù)據(jù)，有的適用于小容量的數(shù)據(jù).

快速排序算法是著名計算機(jī)算法大師Tone Hoare在1960年發(fā)表的，是目前為止基于關(guān)鍵字比較的排序算法中平均性能最佳的排序算法，它的平均時間復(fù)雜度是O(nlogn)，最壞情況下的時間復(fù)雜度是O(n2).

1 相異密度因子

地址映射計數(shù)排序算法是非比較排序算法的典型例子，它的基本思想是：

假設(shè)待排序的元素個數(shù)是n個，記為A[n]，并且這些元素都是正整數(shù)，其中最小的元素是1，最大的元素為m.則算法過程是：1)申請能存放m個正整數(shù)的空間，Temp[m];2)初始化,使得Temp[i]=0，i=1～m;3)對所有的i=1～n, 進(jìn)行Temp[A[i]]=Temp[A[i]]+1;4)定義變量sum=1;5)i從1變化到m,如果Temp[i]≠0，那么j從sum變化到sum+Temp[i]-1，使得每個A[j]=i，然后，sum=sum+Temp[i].

很顯然，時間復(fù)雜度T(n)為上述5個步驟的CPU時間之和.

T(n)=O(1)+O(m)+O(n)+O(1)+O(m)=O(m)+O(n)

(1)

由于n個元素分布在1～m之間，而且這n個元素中可能存在相同的元素，假設(shè)這n個元素中互不相同的相異元素個數(shù)是k個，顯然有，1≤k≤n，且k≤m.

(2)

和快速排序算法比較起來，對于情況1)，顯然快速排序算法比地址映射計數(shù)排序算法要慢；對于情況2)，考慮兩種算法所用CPU時間相同的特殊情況，這時有：

(3)

2 實驗結(jié)果

顯然，快速排序算法和地址映射計數(shù)排序算法兩者即可以用串行計算方法實現(xiàn)，也可以用并行計算方法實現(xiàn)，這里采用串行計算方法實現(xiàn)和比較兩個算法；同時，實現(xiàn)的過程全部在內(nèi)存中進(jìn)行，采用普通PC機(jī)作為實驗對象，CPU為AMD AthlonTM64 X2 Dual Core Processor 5200+2.7 GHz,1.75 GB的內(nèi)存，編程語言采用VC++6.0.

實驗用的數(shù)據(jù)范圍1～m，元素個數(shù)為n，其中，n=10～10000000,m=10～270000000，所有的元素值都是由VC++的隨機(jī)函數(shù)產(chǎn)生.實驗分為5個小的實驗：

1)取m=n，n的范圍為10～20000000，其中10～10000000獨(dú)立運(yùn)行了1次，而n=10000000和n=20000000，則分別運(yùn)行了107次和119次(隨機(jī)次數(shù))，快速排序算法和地址映射計數(shù)排序算法的運(yùn)行時間見表2，由表1可知，快速排序算法的運(yùn)行時間比地址映射計數(shù)排序算法要長的多.

2)取m=n*log2n，n的范圍為2p，(p=1～7)，運(yùn)行次數(shù)是4次，計算出平均運(yùn)行時間，見表3，由表2可知，快速排序算法的運(yùn)行時間和地址映射計數(shù)排序算法有所接近.

表2 當(dāng)n=m時，兩種算法的平均運(yùn)行時間和運(yùn)行次數(shù)

表3 當(dāng)m=n*log2n時，兩種算法的平均運(yùn)行時間和運(yùn)行次數(shù)

3)取n=1000000，m=n*p，(p=1～29)，α=1/p，Y軸是兩種算法運(yùn)行12次的總運(yùn)行時間，X軸是p的遞增值.運(yùn)行結(jié)果見圖2，基本水平的線是快速排序算法的運(yùn)行時間，而基本保持一定斜率的線是地址映射計數(shù)排序算法的運(yùn)行時間，它們在p=21的時候相交.

圖1 當(dāng)n=1000000,m=n/α,兩種算法重復(fù)運(yùn)行12次的結(jié)果

圖2 當(dāng)n=10000000,m=n/α,兩種算法重復(fù)運(yùn)行10次的結(jié)果

4)取n=10000000，m=n*p，(p=1～27)，α=1/p，Y軸是兩種算法運(yùn)行10次的總運(yùn)行時間，X軸是p的遞增值.運(yùn)行結(jié)果見圖3，基本水平的線是快速排序算法的運(yùn)行時間，而基本保持一定斜率的線是地址映射計數(shù)排序算法的運(yùn)行時間，它們在p=23的時候相交.

5)取n=1000000*q，(q=1～10)，對于每個n，取m=n*p，(p=1～27)，α=1/p.對于每個n，存在一個p，記為p′，使得快速排序算法的運(yùn)行時間(T1)p和地址映射計數(shù)排序算法的運(yùn)行時間(T2)p的差滿足4個條件：

|(T1)p′-(T2)p′|≤|(T1)p-1-(T2)p-1|

(4)

|(T1)p′-(T2)p′|≤|(T1)p+1-(T2)p+1|

(5)

(T1)p-1-(T2)p-1≥0

(6)

(T1)p+1-(T2)p+1≤0

(7)

和p′相應(yīng)的α記為α′.

通過觀察實驗，得到了不同n能滿足(4)-(7)的p′，見表4，可以發(fā)現(xiàn)，相異密度因子α和1/log2n，比較接近.

通過實驗，驗證了式(3)是成立的.

表4 當(dāng)兩種算法運(yùn)行時間的絕對值差最小時，α的值和1/log2n的比較表

3 結(jié) 論

快速排序算法是最出色的排序算法之一，廣泛應(yīng)用于計算機(jī)的各個應(yīng)用領(lǐng)域，而當(dāng)元素的個數(shù)n和元素的關(guān)鍵字大小范圍m的比例α滿足：α>log2n時，它比地址映射計數(shù)排序算法的運(yùn)行時間長，因此，如果待排序的數(shù)據(jù)滿足α>log2n時，可采用地址映射計數(shù)排序算法，反之可采用經(jīng)典的快速排序算法.

隨著計算機(jī)技術(shù)飛速發(fā)展，新的排序算法不斷發(fā)現(xiàn)，如縱橫多路并行歸并算法[9]、基于編號的選擇算法[10]、基于完全K叉樹的適應(yīng)性堆排序算法[11]等等，探索面向不同應(yīng)用領(lǐng)域排序算法是新的研究方向.

[1] 維基百科.排序算法[EB/OL].(2008-08-01)[2010-01-11].http://zh.wikipedia.org/zh-cn/排序算法.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言)[M].北京:清華大學(xué)出版社,1997:264-285.

[3] Sedgewick R. Algorithms in C++[M]. MA USA: Addison Wesley Publishing Company,1998:191-193.

[4] Aho, Hopcroft, Ullman. The Design and Analysis of Computer Algorithm[M]. MA USA: Addison Wesley Publishing Company,2003:76-100.

[5] 楊大順，顧蕓瑛.按字節(jié)桶分配鏈接排序法[J].計算機(jī)研究與發(fā)展,1996,33(2):132-139.

[6] Neubert Karl-Dietrich. The Flashsort Algorithm[J]. Dr. Dobb’s Journal,1998(2):123-129.

[7] 唐向陽.分段快速排序算法[J].軟件學(xué)報,1993,4(2):53-57.

[8] 楊紅穎，王向陽.任意分布數(shù)據(jù)的二次分“檔”鏈接排序算法研究[J].小型微型計算機(jī)系統(tǒng),2000,12(19):993-996.

[9] 王穎，李肯立，李浪,等.縱橫多路并行歸并算法[J].計算機(jī)研究與發(fā)展，2006，43(12)：2180-2185.

[10] 原民民，董建剛.一種改進(jìn)的基于編號的選擇排序方法[J].科學(xué)技術(shù)與工程，2009，9(1):139-142.

[11] 蒲保興，陶世群.基于完全K叉樹的適應(yīng)性堆排序算法[J].山西大學(xué)學(xué)報:自然科學(xué)版,2008,31(2)：167-172.