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

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

两类网络连接问题中的最小费用算法及其应用

利用MergeSort算法对加权图中任意两点之间的权值进行排序,把这些权值从小到大进行排列放在一个队列,再利用Kruskal算法求该队列的最小生成树,并将该方法运用于城市交通网络的费用计算;而对于供水管道铺设的最小费用问题可通过最小树形图算法来解决。