在该算法中,针对其中的计算部分(1)中的快速排序的代价为O( klogk),其中k=n/p; 第(2)步中各个处理器选择P个主元的代价为0(P);(3中对P2个主元进行归并并选取新的主 元所需代价为0(F+1ogP;(5)中对数据划分的代价为O(Pm/):最后第()步中各个处理 器进行并行归并的代价为0(m+logP)。针对通信部分(3)中处理器P收集P个主元的代价 为0(門);(4)中播送新选择的P个主元的代价为0(P);最后第(6)步的多对多播送的通信 复杂度与具体的算法实现相关,其最大不会超过O(n)。 MPI源程序请参见章末附录 14小结 本章主要讨论了几个典型的并行排序算法,关于枚举匹配算法的具体讨论可参考[1]: 快速排序算法可以参考文献[2]和[3]中的介绍:文献[4]和[5]讨论了FSRS排序算 参考文献 [1]. Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis de franch [2]. Lorin H Sorting and sort systems. Don Mills, Ontario: Addison-Wesley, 1975, 347-365 [3].陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,200211 [4]. Shi H, Schaeffer J Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 5]. LiX, Lu P, Schaeffer J, Shillington J, Wong PS, Shi H On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993 附录PSRs算法MP源程序 1.源程序 psrs_ sortc #include <stdio h> long DataSize #include <stdlib.h> #include <mpi.h> int mylength; #define INIt TYPe 10 int*temp1; #define ALLtooNE type 1 #define ONETOALL TYPe 200 main(int arge, char'argvD #define MUlti TYPe 300 #define RESULt TYPE 400 long BaseNum=1; #define result len 500 #define multi len 6005 在该算法中，针对其中的计算部分⑴中的快速排序的代价为 O（klogk），其中 k=n/p； 第⑵步中各个处理器选择 P 个主元的代价为 O（P）；⑶中对 P 2 个主元进行归并并选取新的主 元所需代价为 O（P 2 +logP）；⑸中对数据划分的代价为 O（P+n/p）；最后第⑺步中各个处理 器进行并行归并的代价为 O（n/p+logP）。针对通信部分⑶中处理器 P0 收集 P 2 个主元的代价 为 O（P 2 ）；(4)中播送新选择的 P 个主元的代价为 O（P）；最后第(6)步的多对多播送的通信 复杂度与具体的算法实现相关，其最大不会超过 O（n）。 MPI 源程序请参见章末附录。 1.4 小结 本章主要讨论了几个典型的并行排序算法，关于枚举匹配算法的具体讨论可参考［1］； 快速排序算法可以参考文献［2］和［3］中的介绍；文献［4］和［5］讨论了 PSRS 排序算 法。 参考文献 [1]. Chabbar E, Controle, gestion du parallelisme: tris synchrones et asynchrones. Thesis Universite de Franche-comte, France:1980 [2]. Lorin H. Sorting and sort systems. Don Mills, Ontario: Addison-Wesley, 1975, 347~365 [3]. 陈国良 编著. 并行算法的设计与分析（修订版）. 高等教育出版社, 2002.11 [4]. Shi H, Schaeffer J. Parallel Sorting by Regular Sampling. Journal of Parallel and Distributed Computing, 14(4), 1992 [5]. Li X, Lu P, Schaeffer J, Shillington J, Wong P S, Shi H. On the Versatility of Parallel Sorting by Regular Sampling. Parallel Computing, 19, 1993 附录 PSRS 算法 MPI 源程序 1. 源程序 psrs_sort.c #include <stdio.h> #include <stdlib.h> #include <mpi.h> #define INIT_TYPE 10 #define ALLTOONE_TYPE 100 #define ONETOALL_TYPE 200 #define MULTI_TYPE 300 #define RESULT_TYPE 400 #define RESULT_LEN 500 #define MULTI_LEN 600 int Spt; long DataSize; int *arr,*arr1; int mylength; int *index; int *temp1; main(int argc,char* argv[]) { long BaseNum = 1; int PlusNum; int MyID; MPI_Init(&argc,&argv);