均匀划分技术 划分方法 n个元素A[1.n分成p组，每组A[i-1)n/p+1.in/p,i=1~p 米 示例：MIMD-SM模型上的PSRS排序 begin (I)均匀划分：将n个元素A[1n均匀划分成p段，每个p:处理 A[-1)n/p+1.in/p] (2)局部排序：p调用串行排序算法对A[-1)n/p+1.in/p排序 (3)选取样本：p:从其有序子序列A[-1)n/p+1.in/p]中选取p个样本元素 (4)样本排序：用一台处理器对个样本元素进行串行排序 (⑤)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他p (⑥)主元划分：p按主元将有序段A[-1)n/p+1in/p划分成p段 (⑦全局交换：各处理器将其有序段按段号交换到对应的处理器中 (⑧)归并排序：各处理器对接收到的元素进行归并排序 end. 2011/10/25 划分方法 n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p  示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理 A[(i-1)n/p+1..in/p] (2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序 (3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素 (4)样本排序：用一台处理器对p 2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end. 8 2011/10/25 均匀划分技术