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

摘要

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