PSRS算法（Parallel Sorting by Regular Sampling）：首先设待处理里序列长n，并行机上有p个处理器。为了使问题简单，我们假设n是p的整倍数。于是将这n个元素划分为p段，每段中有n/p个元素，将这p段分给p个处理器。注意，执行PSRS算法的并行机必须是多指令流多数据流（MIMD）的。
psrs算法, 目录, 问题的初步处理, 算法描述, 算法分析, 参阅问题的初步处理, 编辑, parallel, sorting, regular, sampling, 首先设待处理里序列长n, 并行机上有p个处理器, 为了使问题简单, 我们假设n是p的整倍数, 于是将这n个元素划分为p段, 每段中有n, p个元素, 将这p段分给p个处理器, 注意, 执行的并行机必须是多指令流多数据流, mimd, 算法描述, 编辑让各个处理器并行的调用串行排序算法进行局部排序, 从每个有序段中选p个样本元素, 共p, disp. 目录 1 问题的初步处理 2 算法描述 3 算法分析 4 参阅问题的初步处理 编辑PSRS算法 Parallel Sorting by Regular Sampling 首先设待处理里序列长n 并行机上有p个处理器 为了使问题简单 我们假设n是p的整倍数 于是将这n个元素划分为p段 每段中有n p个元素 将这p段分给p个处理器 注意 执行PSRS算法的并行机必须是多指令流多数据流 MIMD 的 算法描述 编辑让各个处理器并行的调用串行排序算法进行局部排序 从每个有序段中选p个样本元素 共p 2 displaystyle p 2 nbsp 个样本元素 采样 对样本元数排序 从样本元素中选p 1作为划分元素 并播送给其余的处理器 各个处理器根据划分元素对局部序列进行划分 分为p段 各个处理器将每一段按段号交换到相应序列号的处理器 在各个处理器中使用串行算法再次进行局部排序 算法分析 编辑如果注意到一个好的串行排序算法的时间复杂度为O n l o g n displaystyle O nlogn nbsp 那么 容易证得上述PSRS算法的时间复杂度在n gt p 3 displaystyle n gt p 3 nbsp 时为O n p l o g n displaystyle O frac n p log n nbsp 缺点 我们注意到 在第五步进行主元划分时时可能会引起不均匀性 即位于某两个主元之间的元素可能要多一些 多于n p displaystyle frac n p nbsp 个 我们可以证明 在算法中进行到第六步全局交换时 可能会有某一个处理器中数据达到2 n p n p 2 p 1 displaystyle frac 2n p frac n p 2 p 1 nbsp 个 这样引起的直接后果是处理器负载不均匀 那么在归并排序中可能会引起排序时间的不均匀 参阅 编辑并行计算 并行排序 取自 https zh wikipedia org w index php title PSRS算法 amp oldid 50277896, 维基百科，wiki，书籍，书籍，图书馆，
