奇偶置换冒泡排序的并行化

　　奇偶置换冒泡排序很容易并行化，在算法的每个阶段，每对元素的比较可以并行完成而互不干扰。程序6.2.6给出了并行化后的程序伪码，代码假定处理器数目等于待排序的元素数目。下面来分析一下并行算法的加速比和效率。设处理器数目为p（p≤n），每个处理器上有n/p个元素构成一个超元素。首先，各个处理器对自己的元素进行内部排序，利用目前最快的串行算法，时间复杂度为。然后，每个处理器都执行p步操作（p/2步奇操作和p/2步偶操作）来与相邻的处理器进行元素交换。每步操作需要次比较操作和的通信时间。所以总的并行处理时间是：
　　　　
　　因为串行处理时间是，因此得到算法的加速比S和效率E分别为：
　　
　　

　　从上述式子可以看出，将效率维持在一定水平的条件是，这说明当要求效率固定时，为了增加一台处理器，任务（即待排序的元素数目）需要呈指数增加，因此算法的可扩展性比较差。
　　
　　　　　　　　　　　　　奇偶置换排序的示例

　　
　　　　　　　　　　　　　并行奇偶置换排序算法