多核计算环境下的桶排序算法优化

编号 zgly0000922249

文献类型 期刊论文

文献题名 多核计算环境下的桶排序算法优化

作者 康志辉 

作者单位 厦门软件职业技术学院 

母体文献 长春师范大学学报 

年卷期 2015(8)

页码 39-43

年份 2015 

关键词 桶排序  归并排序  流水线技术  并行算法 

文摘内容 经典并行桶排序算法的时间复杂度为O((n/p)*log(n/p)),其前提要求原始数据是在一个已知的间隔内均匀分布时,才有良好的效果。对非均匀分布的数据进行排序,最坏排序时间为O(n*logn),即退化成为串行的快速排序算法。为了解决该算法对原始数据的约束,本文提出一种改进的并行桶排序算法,对原始数据的划分不是根据数据在已知间隔中的位置,而是根据数据在序列上的位置划分数据。引入一种新的2-路归并算法,并且运用了流水线思想,设置任意分布数据排序的时间复杂度为O((n/p)*log(n/p))。