童小明

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

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

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；//在静态链表中实现插入在队列尾部