最快的內(nèi)部排序法—桶排序法

童小明

摘要：排序方法非常重要，但是種類很多，現(xiàn)在最快的內(nèi)部排序方法是快速排序，但是本人仔細(xì)研究了桶式排序法，理論上它應(yīng)該比快速排序法還要快，但實際應(yīng)用中卻比快速排序慢一些，尤其是當(dāng)數(shù)據(jù)量非常大時。于是本人改進了桶式排序法，并命名為桶排序法，非常簡單高效，時間復(fù)雜度也很低，是最快的內(nèi)部排序法。

關(guān)鍵詞：內(nèi)部排序時間復(fù)雜度空間復(fù)雜度快速排序桶排序

0. 引言

排序方法非常重要，但是種類很多，現(xiàn)在最快的內(nèi)部排序方法是快速排序，但是本人仔細(xì)研究了桶式排序法，理論上它應(yīng)該比快速排序法還要快，但實際應(yīng)用中卻比快速排序慢一些，尤其是當(dāng)數(shù)據(jù)量非常大時。

于是本人改進了桶式排序法，并命名為桶排序法，非常簡單高效，時間復(fù)雜度也很低，是最快的內(nèi)部排序法。

中學(xué)高級教師，軟件編程和算法設(shè)計

1.桶式排序法

桶式排序過程示例。

問題（1）的解決：桶式排序法采用鏈接存儲，設(shè)置m個鏈隊列作為桶的存儲結(jié)構(gòu)。

采用靜態(tài)鏈表作為鏈隊列和待排序記錄序列的存儲結(jié)構(gòu)。

structNode{

intkey；//鍵值

intnext；//下一個鍵值在數(shù)組中的下標(biāo)

}；

structQueueNode{//定義靜態(tài)鏈隊列存儲桶

intfront；//隊頭指針

intrear；//隊尾指針

}

問題（2）的解決：分配操作即是將記錄插入到相應(yīng)的隊列中，入隊在靜態(tài)鏈表上實現(xiàn)，

并修改相應(yīng)隊列的隊頭指針和隊尾指針。

//分配算法

//first為靜態(tài)鏈表的頭指針，從下標(biāo)0開始存放待排序序列

voidDistribute（Noder[]，intn，QueueNodeq[]，intm，intfirst）

{

i=first；

while（r[i].next！=-1）//依次分配每一個待排序記錄

{

k=r[i].key；

if（q[k].front==-1）q[k].front=i；//處理隊列為空的情況

elser[q[k].rear].next=i；//在靜態(tài)鏈表中實現(xiàn)插入在隊列尾部

q[k].rear=i；//修改隊尾指針

i=r[i].next；//i后移，處理下一個記錄

}

}

桶式排序法的時間復(fù)雜度小，但是空間復(fù)雜度大，而且算法很復(fù)雜。

2.桶排序法

（1）如何表示桶？即如何存儲具有相同鍵值的記錄？

通過創(chuàng)建一個結(jié)構(gòu)體的堆數(shù)組（隊列）來實現(xiàn)，

structqueue{

intcount2；//重復(fù)元素的個數(shù)

queue（）{count2=0；}

}；

queue*Q；//隊列（待分配）

將每一個數(shù)對應(yīng)到它的值所在隊列位置中。

比如，定義queueQ[10000]；

表示最大的數(shù)是9999，最小的數(shù)是0。

（2）如何進行分配操作？

如果數(shù)是1000，則Q[1000].count2=1；

如果下一個數(shù)是1，則Q[1].count2=1；

對于一個新出現(xiàn)的數(shù)，則隊列相應(yīng)位置的計數(shù)為1。

如果遇到以前出現(xiàn)的數(shù)，則相應(yīng)位置的計數(shù)加1，

比如下一個數(shù)是1000，則

Q[1000].count2=2，

出現(xiàn)幾次，計數(shù)就累加1幾次，即count2表示該位置表示的數(shù)出現(xiàn)的次數(shù)。

2.1桶排序法使用的全部變量和結(jié)構(gòu)體定義

structqueue{

intcount2；//重復(fù)元素的個數(shù)

queue（）{count2=0；}

}；

inta[450000001]；

intn；

intmaxValue，minValue，base；//如果minValue<0，base=-minValue；否則base=0

queue*Q；//隊列（待分配）

2.2桶排序法的初始化

voidInit（）

{

maxValue=-0x7f7f7f7f，minValue=-maxValue；

n=300000000；

for（inti=0；i

{

a[i]=n-i；//rand（）+1000；

if（i%2==0）a[i]*=-1；

if（a[i]>maxValue）maxValue=a[i]；

if（a[i]

}

//分配maxValue+base+1個桶

base=（minValue>=0）？0：-minValue；//保證下標(biāo)>=0

try{

Q=newqueue[maxValue+base+1]；

}

catch（constbad_alloc&e;）

{

cout<<"內(nèi)存分配錯誤！"<

exit（1）；

}

cout<<"初始數(shù)據(jù)如下"<

if（n<=10000）Output（a，n）；

3、海量數(shù)據(jù)的桶排序法

如果數(shù)據(jù)量太大，則內(nèi)存無法容納這么多數(shù)據(jù)，一般的方法是使用外部排序，但是外部排序需要頻繁讀寫磁盤，耗時非常大，

效率很低。有沒有更好的方法可以實現(xiàn)呢？

3.1內(nèi)存映射文件

對于幾十GB、幾百GB、乃至幾TB的海量存儲，以通常的文件處理方法進行處理是不行的。一般用內(nèi)存映射文件處理。

內(nèi)存映射文件，是由一個文件到一塊內(nèi)存的映射。Win32提供了允許應(yīng)用程序把文件映射到一個進程的函數(shù)（CreateFileMapping）。內(nèi)存映射文件與虛擬內(nèi)存有些類似，通過內(nèi)存映射文件可以保留一個地址空間的區(qū)域，同時將物理存儲器提交給此區(qū)域，內(nèi)存文件映射的物理存儲器來自一個已經(jīng)存在于磁盤上的文件，而且在對該文件進行操作之前必須首先對文件進行映射。使用內(nèi)存映射文件處理存儲于磁盤上的文件時，將不必再對文件執(zhí)行I/O操作，使得內(nèi)存映射文件在處理大數(shù)據(jù)量的文件時能起到相當(dāng)重要的作用。

3.2巨型內(nèi)存需要的全局變量

HANDLEhMapfile；

HANDLEhMapview；

unsignedchar*pbyte；

charfilename[]="h：＼＼bucketSort.txt"；//保證H盤有300G自由空間

longlongsize；

int*a；

boolfinished；

說明，要事先準(zhǔn)備一個大容量硬盤，比如300G的硬盤，盤符設(shè)為H：。巨型內(nèi)存分配后，就可以把a[]當(dāng)成超大數(shù)組使用了。

當(dāng)然硬盤容量越大，能夠使用的虛擬內(nèi)存也就越多，但是也需要機器的配置很高，才能體現(xiàn)出本算法的性能優(yōu)勢。

4.小結(jié)

內(nèi)部排序法很多，時間復(fù)雜度和空間復(fù)雜度各不相同，而且難易程度巨大。

對于我們，首先應(yīng)該選擇時間復(fù)雜度小的內(nèi)部排序法；

在滿足此前提下，應(yīng)選擇算法簡單的內(nèi)部排序法；

在滿足前兩個前提下，應(yīng)選擇空間復(fù)雜度小的內(nèi)部排序法；

在滿足前三個前提下，應(yīng)選擇穩(wěn)定排序法。

由此我們得出，桶排序法是迄今為止最快最好的內(nèi)部排序法。

參考文獻：

[1]陳銳.新C/C++函數(shù)與算法速查速用大辭典[Z].北京：中國鐵道出版社，2015.