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

童小明

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

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

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）；