最快的內部排序法—桶排序法

童小明

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

關鍵詞：內部排序時間復雜度空間復雜度快速排序桶排序

0. 引言

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

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

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

1.桶式排序法

桶式排序過程示例。

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

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

structNode{

intkey；//鍵值

intnext；//下一個鍵值在數組中的下標

}；

structQueueNode{//定義靜態鏈隊列存儲桶

intfront；//隊頭指針

intrear；//隊尾指針

}

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

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

//分配算法

//first為靜態鏈表的頭指針，從下標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；//在靜態鏈表中實現插入在隊列尾部

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

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

}

}

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

2.桶排序法

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

通過創建一個結構體的堆數組（隊列）來實現，

structqueue{

intcount2；//重復元素的個數

queue（）{count2=0；}

}；

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

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

比如，定義queueQ[10000]；

表示最大的數是9999，最小的數是0。

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

如果數是1000，則Q[1000].count2=1；

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

對于一個新出現的數，則隊列相應位置的計數為1。

如果遇到以前出現的數，則相應位置的計數加1，

比如下一個數是1000，則

Q[1000].count2=2，

出現幾次，計數就累加1幾次，即count2表示該位置表示的數出現的次數。

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

structqueue{

intcount2；//重復元素的個數

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<<"內存分配錯誤！"<

exit（1）；

}

cout<<"初始數據如下"<

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

3、海量數據的桶排序法

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

效率很低。有沒有更好的方法可以實現呢？

3.1內存映射文件

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

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

3.2巨型內存需要的全局變量

HANDLEhMapfile；

HANDLEhMapview；

unsignedchar*pbyte；

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

longlongsize；

int*a；

boolfinished；

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

當然硬盤容量越大，能夠使用的虛擬內存也就越多，但是也需要機器的配置很高，才能體現出本算法的性能優勢。

4.小結

內部排序法很多，時間復雜度和空間復雜度各不相同，而且難易程度巨大。

對于我們，首先應該選擇時間復雜度小的內部排序法；

在滿足此前提下，應選擇算法簡單的內部排序法；

在滿足前兩個前提下，應選擇空間復雜度小的內部排序法；

在滿足前三個前提下，應選擇穩定排序法。

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

參考文獻：

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