论文部分内容阅读
排序问题在计算机的诸多研究领域都具有重要的意义，例如在编译、操作系统、数据库管理系统、路由、置换网络等领域均涉及到和排序有关的问题。据估计，计算机所完成的所有工作中，有25％～50％与数据的排序有关。因此，对排序问题的研究具有广泛的实用价值和重要的理论意义。 本文首先综述了现阶段并行排序算法的研究与发展情况，指出对基于归并的排序算法的研究是排序领域的重要方向之一。目前对基于归并的排序算法的研究中，大都以2-sorters为其基本构件，即两个数的比较交换。因此，一个最为直接的问题是：如果排序算法不是基于2-sorters，而是完全基于k-sorters，是否也能实现排序呢?这里k-sorters是指一次完成k个数的排序，k为大于等于2的任意整数。如果能够利用k-sorters来实现排序，那么这种排序算法和基于2-sorters的排序算法相比会有什么样的特点、会带来什么样的好处呢?虽然对上述问题的研究吸引了很多计算机研究人员的兴趣，而且也有了部分的答案，但对该问题较为彻底的解决目前在国内外尚未见报导。本文对此进行了深入的研究，具体研究成果如下： 第一，我们给出了一个完全基于k-sorters的多路归并算法--ISS-Mk算法，其中k可以为任意整数。ISS-Mk算法彻底撇开了归并算法对2-sorters的依赖，而是完全基于k-sorters，而且k可以是任一大于等于2的自然数。在ISS-Mk排序算法的基础上，我们还给出了相应的并行排序算法--ISS-Sk算法。 第二，在基于k-sorters的多路归并算法ISS-Mk中，我们采用了倾斜与振荡的方法和分块的方法相结合的策略。在对多路归并算法的研究中，虽然也出现了完全基于k-sorters的多路归并算法--SS-Mk算法，但SS-Mk算法要求k必须为素数，因此这时的多路归并并不能做到任意路的归并。 第三，在基于k-sorters的多路归并算法SS-Mk和ISS-Mk的基础上，我们提出了相应的排序网络，并且作为实例，我们具体设计了N=27、k=3、