基于串行計算的排序算法實證分析

陳根方，張立印

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

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

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

0 前 言

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

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

表1 常見的排序算法

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

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

1 相異密度因子

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

假設待排序的元素個數(shù)是n個，記為A[n]，并且這些元素都是正整數(shù)，其中最小的元素是1，最大的元素為m.則算法過程是：1)申請能存放m個正整數(shù)的空間，Temp[m];2)初始化,使得Temp[i]=0，i=1～m;3)對所有的i=1～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].

很顯然，時間復雜度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個元素中可能存在相同的元素，假設這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)存中進行，采用普通PC機作為實驗對象，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++的隨機函數(shù)產(chǎn)生.實驗分為5個小的實驗：

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

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

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

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

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

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

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

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

5)取n=1000000*q，(q=1～10)，對于每個n，取m=n*p，(p=1～27)，α=1/p.對于每個n，存在一個p，記為p′，使得快速排序算法的運行時間(T1)p和地址映射計數(shù)排序算法的運行時間(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′相應的α記為α′.

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

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

表4 當兩種算法運行時間的絕對值差最小時，α的值和1/log2n的比較表

3 結(jié) 論

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

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

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

[2] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言)[M].北京:清華大學出版社,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].計算機研究與發(fā)展,1996,33(2):132-139.

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

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

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

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

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

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