(1.6)Pid+2m- send data(r+1, m-1] back to Pid end if 在最优的情况下该并行算法形成一个高度为logn的排序树,其计算复杂度为O(n), 通信复杂度也为O(n)。同串行算法一样,在最坏情况下其计算复杂度降为O(n2)。正常 情况下该算法的计算复杂度也为O(n),只不过具有更高的常数因子 MPI源程序请参见所附光盘 13PsRS排序 131PSRS算法原理 并行正则采样排序,简称PSRS( Parallel Sorting by Regular Sampling)它是一种基 于均匀划分( Uniform Partition)原理的负载均衡的并行排序算法。假定待排序的元素有 n个,系统中有p个处理器,那么系统首先将n个元素均匀地分割成p段,每段含有n/p个 元素,每段指派一个处理器,然后各个处理器同时施行局部排序。为了使各段中诸局部有序 的元素在整个序列中也能占据正确的位置,那么就首先从各段中抽取几个代表元素,再从他 们产生出p-1个主元,然后按这些主元与原各局部有序中的元素之间的偏序关系,将各个局 部有序段划分成p段,接着通过全局交换将各个段中的对应部分集合在一起,最后将这些集 合在一起的各部分采用多路归并的方法进行排序,这些有序段汇合起来就自然成为全局有序 序列了。 132PSRs算法形式化描述 设有n个数据,P个处理器,以及均匀分布在P个处理器上的n个数据。则PSRS算法 可描述如下: 算法135PsRS排序算法 输入:n个待排序的数据,均匀地分布在P个处理器上 输出:分布在各个处理器上,得到全局有序的数据序列 Begin 1)每个处理器将自己的n/P个数据用串行快速排序( Quicksort),得到一个排好序的 序列 (2)每个处理器从排好序的序列中选取第W,2w,3w,…,(P-1)w个共P-1个数据作为 代表元素,其中w=n/P2; (3)每个处理器将选好的代表元素送到处理器P。中,并将送来的P段有序的数据序列 做P路归并,再选择排序后的第P-1,2(P-1),…,(P-1)(P-1)个共P-1个主元; (4)处理器P将这P-1个主元播送到所有处理器中 (5)每个处理器根据上步送来的P-1个主元把自己的n/P个数据分成P段,记w!为处 理器P的第j1段,其中i=0,…,P-1,j=0, (6)每个处理器送它的第i+1段给处理器P,从而使得第i个处理器含有所有处理器的 第i段数据(i=0,…,P-1) (7)每个处理器再通过P路归并排序将上一步的到的数据排序:从而这n个数据便是有 End4 (1.6)Pid+2m-1 send data[r+1,m-1] back to Pid end if End 在最优的情况下该并行算法形成一个高度为 logn 的排序树，其计算复杂度为 O（n）， 通信复杂度也为 O（n）。同串行算法一样，在最坏情况下其计算复杂度降为 O（n 2）。正常 情况下该算法的计算复杂度也为 O（n），只不过具有更高的常数因子。 MPI 源程序请参见所附光盘。 1.3 PSRS 排序 1.3.1 PSRS 算法原理 并行正则采样排序，简称 PSRS(Parallel Sorting by Regular Sampling)它是一种基 于均匀划分（Uniform Partition）原理的负载均衡的并行排序算法。假定待排序的元素有 n 个，系统中有 p 个处理器，那么系统首先将 n 个元素均匀地分割成 p 段，每段含有 n/p 个 元素，每段指派一个处理器，然后各个处理器同时施行局部排序。为了使各段中诸局部有序 的元素在整个序列中也能占据正确的位置，那么就首先从各段中抽取几个代表元素，再从他 们产生出 p-1 个主元，然后按这些主元与原各局部有序中的元素之间的偏序关系，将各个局 部有序段划分成 p 段，接着通过全局交换将各个段中的对应部分集合在一起，最后将这些集 合在一起的各部分采用多路归并的方法进行排序，这些有序段汇合起来就自然成为全局有序 序列了。 1.3.2 PSRS 算法形式化描述 设有 n 个数据，P 个处理器，以及均匀分布在 P 个处理器上的 n 个数据。 则 PSRS 算法 可描述如下： 算法 13.5 PSRS 排序算法 输入：n 个待排序的数据，均匀地分布在 P 个处理器上 输出：分布在各个处理器上，得到全局有序的数据序列 Begin (1) 每个处理器将自己的 n/P 个数据用串行快速排序(Quicksort)，得到一个排好序的 序列； (2) 每个处理器从排好序的序列中选取第 w，2w，3w，…，(P-1)w 个共 P-1 个数据作为 代表元素，其中 w=n/P2； (3) 每个处理器将选好的代表元素送到处理器 P0 中，并将送来的 P 段有序的数据序列 做 P 路归并，再选择排序后的第 P-1，2(P-1)，…，(P-1)(P-1)个共 P-1 个主元； (4) 处理器 P0 将这 P-1 个主元播送到所有处理器中； (5) 每个处理器根据上步送来的 P-1 个主元把自己的 n/P 个数据分成 P 段，记 j wi 为处 理器 Pi 的第 j+1 段，其中 i=0，…，P-1，j=0，…，P-1； (6) 每个处理器送它的第 i+1 段给处理器 Pi，从而使得第 i 个处理器含有所有处理器的 第 i 段数据(i=0，…，P-1)； (7) 每个处理器再通过 P 路归并排序将上一步的到的数据排序；从而这 n 个数据便是有 序的。 End