基于数组的桶排序算法

经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(NlogN)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(NlogN)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Lin-ux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用.

桶外排序算法的抽样分点分发策略

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.