摘要: 自从1968年Batcher的排序网络发表后,已经有很多文章对它作了进一步的研究。然而有关从n个数中选出m个最小的所谓选择网络却很少有研究。本文提出了一种基于双调（bitonic）序列和分组原理的并行选择算法,并给出了相应的使用Batcher的基本比较元件实现的具体选择网络。所提出的选择网络分别具有O（n·log²m）和O（logn·logm）²的硬件和时间的复杂度。与Alekseyev的选择网络相比,平均加速是O（logm）。并且首次表明了:使用Batcher的基本比较元件所构成的选择网络,其硬件和时间复杂度将小于相应的Batcher的排序网络的复杂度。