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

童小明

摘要：排序方法非常重要，但是种类很多，现在最快的内部排序方法是快速排序，但是本人仔细研究了桶式排序法，理论上它应该比快速排序法还要快，但实际应用中却比快速排序慢一些，尤其是当数据量非常大时。于是本人改进了桶式排序法，并命名为桶排序法，非常简单高效，时间复杂度也很低，是最快的内部排序法。

关键词：内部排序时间复杂度空间复杂度快速排序桶排序

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.