導(dǎo)語：計數(shù)查找算法研究論文一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

1算法的基本思想

通常的排序算法在空間和時間復(fù)雜度一定的情況下的時間開銷主要是關(guān)鍵字之間的比較和記錄的移動。基于計數(shù)排序的查找算法（Count-Search）的實現(xiàn)在整個過程無需進行數(shù)據(jù)的比較，算法的時間復(fù)雜度為O(2*N)。該算法的基本原理是：

根據(jù)無符號整數(shù)的大小可以和數(shù)組元素的下標對應(yīng)的原則，在程序中可以用整數(shù)數(shù)組來儲存元素的大小關(guān)系。對于一個大小為N的整型數(shù)組a[]，對于每一個元素x，用數(shù)組中的元素a[x]記錄下小于等于它的元素個數(shù)，當要找的是集合中第K個大的元素時，則只需找到該數(shù)組中第N-K+1小的元素。即只需要找到該數(shù)組中第一個大于或等于N-K+1的元素，該元素的下標即為第K大的數(shù)。

該算法具體可以描述為：假設(shè)n個輸入元素的每一個都是介于0到M之間的整數(shù)，此處M為某個無符號整數(shù)。

(1)對于每一個輸入的元素X，首先確定出等于X的元素個數(shù)。

(2)對于每一個元素X，確定小于等于X的元素個數(shù)。

(3)從數(shù)組首地址出發(fā)順序查找到第一個小于等于K的元素，則該元素X即為所要查找的第K小的數(shù)，順序查找到第一個小于等于N-K+1的元素，則該元素X即為所要查找的第K大的數(shù)。

2計數(shù)查找算法的C語言實現(xiàn)(Count—Search)

2.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計與程序

假定輸入的數(shù)組為整型數(shù)組A[1..N]，length[A]=N，數(shù)組中元素最大值為M，數(shù)組C[]記錄整數(shù)元素的大小關(guān)系。

Count-Search(int*A，intK)

memest(C，0)//C[0..M]==0初始化C[]

forj=1tolength[A]

doC[A[j]]=C[A[j]]+1

//C[i]包含等于i的元素個數(shù)

fori=1toM

begin

doC[i]=C[i]+C[i-1]//C[i]包含小于等于i的元素個數(shù)

if(C[i]>=N-K+1)break；//尋找到第N-K+1的元素，即為第K大的元素

end

2.2算法步驟分析

第一步：第一行的初始化操作之后，在2-3行檢查每一個輸入元素。如果一個輸入元素的值為i，即C[i]的值加1。于是在第3行之后，C[i]中存放了等于i的元素個數(shù)（整數(shù)i=0，1，…M）。

第二步：在第4-8之后，C[i]存放了小于等于i的元素的個數(shù)。最后從數(shù)組C的首地址出發(fā)順序查找第一個使得C[i]>=N-K+1的元素，則第K大的元素即為i。

下圖給出了Count-Search的運算過程：圖1表示初始數(shù)組A，C。圖2表示運行完程序2-3行，數(shù)組C中的元素C[i]存放的是數(shù)組A中等于i的元素個數(shù)。圖3表示運行4-8行的結(jié)果，C中元素C[i]存放的是數(shù)組A中小于等于i的元素個數(shù)。例如查找該數(shù)組第3大的數(shù)，則由于C[2]=4>=3，故元素2即為所要查找的第3大的數(shù)。

2.3時間復(fù)雜度分析

程序2-3行時間復(fù)雜度為O(N)，第4-8行時間復(fù)雜度為O(M)，該算法的時間復(fù)雜度為T(n)=O(N+M)。如果數(shù)組A[]的最大值M與N成線形關(guān)系，即M=O(n)，則其時間復(fù)雜度為T(n)=O(2N)。

3Count-Search算法與Divide-Select算法的比較

Divide-Select的基本思想是：通過在線性的時間內(nèi)找到一個劃分基準，使得按這個基準所劃分出的兩個子數(shù)組的長度都至少為原數(shù)組的ξ倍（0<ξ<1是某個正常數(shù)），然后對子數(shù)組遞歸的調(diào)用Divide-Select算法，這樣就可以在線性的時間內(nèi)完成查找任務(wù)。[6]

該算法得時間復(fù)雜度為O(6.09*N)[5]，與Count-Search算法相比較可知：Count-Search算法具有更好的時間復(fù)雜度。

4算法測試與比較

為了證實上述結(jié)論，在ACERTravelMate2420(PM730，512M內(nèi)存，80G硬盤)，WindowsXP平臺上編寫了三種查找算法的子程序，進行了相應(yīng)的實驗測定，其結(jié)果如表1所示。（實驗數(shù)據(jù)全部采用均分布的無符號整型隨機數(shù)）

觀察分析以上實驗結(jié)果，可以看出：基于快速排序的查找算法和其他算法相比較具有較差的效率；而采用了分治策略的Divide-Select查找算法的效率可以是基于快速排序的查找算法的幾十倍，其時間復(fù)雜度在圖中也反映為線性。而基于計數(shù)排序的查找算法（Count-Search）的時間復(fù)雜度同樣達到了線性，但是效率卻比Divide-Select更高，通過上述實驗可以得知：在進行無符號整數(shù)查找時，基于計數(shù)排序的查找算法（Count-Search）在時間上是最優(yōu)的。

5Count-Search的應(yīng)用范圍

在查找無符號整數(shù)集合時，應(yīng)用Count-Search算法，能夠降低查找時間復(fù)雜度。但是應(yīng)用Count-Search算法時要注意：該算法只適用于整數(shù)的查找，且查找集合S的最大值M與S中元素個數(shù)N不成指數(shù)關(guān)系，即M不能遠大于N。因為當M過大時，首先內(nèi)存開銷就會很大，其次時間復(fù)雜度也會相應(yīng)的提高。

該算法充分的運用了整數(shù)的特性，整個運算過程中無需數(shù)據(jù)的比較和交換，大大降低了算法的時間復(fù)雜度，因此該算法可以在工程統(tǒng)計中得到大規(guī)模運用。例如：隨著網(wǎng)絡(luò)的發(fā)展和應(yīng)用，網(wǎng)絡(luò)中的信息量成倍的擴大，而在其中我們關(guān)注的最多的則是統(tǒng)計排名比較靠前的信息，如果將全部過億的統(tǒng)計量排序，則由于數(shù)據(jù)量過大，則會浪費大量的時間和資源。而采用Count-Search的查找算法，就可在線性的時間完成。

6結(jié)束語

本文中提出的一種基于計數(shù)排序算法的整數(shù)查找算法，該算法在運算過程中無需進行數(shù)據(jù)的比較和交換，該算法可以應(yīng)用到大規(guī)模的整數(shù)查找，算法的時間復(fù)雜度很低，而且避免的大量的數(shù)據(jù)比較和交換，同時在時間上是最優(yōu)的。