共 4 条
基于数组的桶排序算法
被引：14
作者：
杨磊
宋涛
机构：
[1] 清华大学计算机科学与技术系
来源：
关键词：
复杂度;
排序算法;
计数排序;
桶排序;
快速排序;
PennySort;
D O I：
暂无
中图分类号：
TP311.12 [];
学科分类号：
081202 ;
0835 ;
摘要：
经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(NlogN)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(NlogN)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Lin-ux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用.
引用
收藏
页码：341 / 347
页数：7
相关论文