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

童小明

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

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

0. 引言

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

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

中學高級教師，軟件編程和算法設計

1.桶式排序法

桶式排序過程示例。

問題（1）的解決：桶式排序法采用鏈接存儲，設置m個鏈隊列作為桶的存儲結構。

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

structNode{

intkey；//鍵值

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

}；

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

intfront；//隊頭指針

intrear；//隊尾指針

}

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

并修改相應隊列的隊頭指針和隊尾指針。

//分配算法

//first為靜態(tài)鏈表的頭指針，從下標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后移，處理下一個記錄

}

}

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

2.桶排序法

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

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

structqueue{

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

queue（）{count2=0；}

}；

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

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

比如，定義queueQ[10000]；

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

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

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

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

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

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

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

Q[1000].count2=2，

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

2.1桶排序法使用的全部變量和結構體定義

structqueue{

intcount2；//重復元素的個數(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；//保證下標>=0

try{

Q=newqueue[maxValue+base+1]；

}

catch（constbad_alloc&e;）

{

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

exit（1）；