查看“︁PSRS算法”︁的源代码

==问题的初步处理==
PSRS算法（Parallel Sorting by Regular Sampling）：首先设待处理里序列长n，并行机上有p个处理器。为了使问题简单，我们假设n是p的整倍数。于是将这n个元素划分为p段，每段中有n/p个元素，将这p段分给p个处理器。注意，执行PSRS算法的并行机必须是[[多指令流多数据流]]（MIMD）的。

== 算法描述 ==
# 让各个处理器并行的调用串行排序算法进行局部排序；
# 从每个有序段中选p个样本元素，共<math>p^2</math>个样本元素（采样）；、
# 对样本元数排序；
# 从样本元素中选p-1作为划分元素，并播送给其余的处理器；
# 各个处理器根据划分元素对局部序列进行划分（分为p段）；
# 各个处理器将每一段按段号交换到相应序列号的处理器；
# 在各个处理器中使用串行算法再次进行局部排序。

== 算法分析 ==
如果注意到一个好的串行排序算法的时间复杂度为<math>O(nlogn)</math>那么，容易证得上述PSRS算法的时间复杂度在<math>n>p^3</math>时为<math>O(\frac{n}{p}log{n})</math>。

'''缺点'''：我们注意到，在第五步进行主元划分时时可能会引起不均匀性，即位于某两个主元之间的元素可能要多一些（多于<math>\frac{n}{p}</math>个）。我们可以证明，在算法中进行到第六步全局交换时，可能会有某一个处理器中数据达到<math>\frac{2n}{p}-\frac{n}{p^2}-(p-1)</math>个；这样引起的直接后果是处理器负载不均匀，那么在归并排序中可能会引起排序时间的不均匀。

== 参阅 ==
[[并行计算]]
[[并行排序]]

[[Category:并发计算]]
[[Category:算法]]