第六节 分配排序

分配排序的基本思想：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序。常用的分配排序有箱排序和基数排序。

一、箱排序

1、箱排序的基本思想

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

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。

2、算法简析

箱排序的时间复杂度为 O(n)。箱排序是稳定排序，箱排序只适用于关键字取值范围较小的情况，否则所需要箱子的数目太多，会导致存储空间的浪费和计算时间的增长。