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

童小明

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

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

0. 引言

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

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

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

1.桶式排序法

桶式排序過程示例。

問題（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ì)尾指針

}

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

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

//分配算法

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

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ǔ)具有相同鍵值的記錄？

通過創(chuàng)建一個(gè)結(jié)構(gòu)體的堆數(shù)組（隊(duì)列）來實(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）；