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

童小明

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

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

0. 引言

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

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

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

1.桶式排序法

桶式排序過(guò)程示例。

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

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

structNode{

intkey；//鍵值

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

}；

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

intfront；//隊(duì)頭指針

intrear；//隊(duì)尾指針

}

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

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

//分配算法

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

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

{

i=first；

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

{

k=r[i].key；

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

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

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

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

}

}

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

2.桶排序法

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

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

structqueue{

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

queue（）{count2=0；}

}；

queue*Q；//隊(duì)列（待分配）

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

比如，定義queueQ[10000]；

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

（2）如何進(jìn)行分配操作？

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

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

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

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

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

Q[1000].count2=2，

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

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

structqueue{

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

queue（）{count2=0；}

}；

inta[450000001]；

intn；

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

queue*Q；//隊(duì)列（待分配）

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個(gè)桶

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

try{

Q=newqueue[maxValue+base+1]；

}

catch（constbad_alloc&e;）

{

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

exit（1）；

}

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

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

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

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

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

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

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

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

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

HANDLEhMapfile；

HANDLEhMapview；

unsignedchar*pbyte；

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

longlongsize；

int*a；

boolfinished；

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

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

4.小結(jié)

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

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

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

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

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

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

參考文獻(xiàn)：

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