箱排序 下载本文

1、箱排序的基本思想

箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…

2、箱排序中,箱子的个数取决于关键字的取值范围。

若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。 链表盲点

4、为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。 (1)实现方法一

每个箱子设为一个链队列。当一记录装入某箱子时,应做入队操作将其插入该箱子尾部;而收集过程则是对箱子做出队操作,依次将出队的记录放到输出序列中。

(2)实现方法二

若输入的待排序记录是以链表形式给出时,出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域,令其指向箱子链表的头,然后修改输出链表的尾指针,令其指向箱子链表的尾即可。

5、算法简析

分配过程的时间是O(n);收集过程的时间为O(m)(采用链表来存储输入的待排序记录)或O(m+n)。因此,箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n),则箱排序的时间是线性的,即O(n)。 注意:

箱排序实用价值不大,仅适用于作为基数排序(下节介绍)的一个中间步骤。