多项选择和分布式排序

MULTI-SELECTION AND DISTRIBUTED SORTING

本文定义了多项选择概念,并给出了串行和分布式多项选择算法以及基于多项选择的分布式排序算法。该分布式排序算法所需要的平均信件数为O(p×max{log_2×log_2p,p}),最坏情况为O(p×n),其中n为要排序的元素个数,p为参加排序的机器台数。因此所提出的算法比现有的分布式排序算法好。

In this paper the concept of multi-selection an.d two multi-selection algorithms, sequential and distributed, are presented. A distributed sorting algorithm based on multi-selection is also given, in which the number of messsages requieed are O(p×max {log2 n×log2 p9 p}) and O(p×n) on the average and on the worst case respectively, where p is the number of computers in distributed sorting and n the n number of elements to be sorted. Therefore the algorithm performs better than the others.