请教一下 奇偶排序 问题

9z本人lz

偶看到一个文章，说到是有个奇偶排序：

    有一种简单排序算法是奇偶排序。它的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j＝1，3，5，…)。如果它们的关键字的值次序颠倒，就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2，4，6，……)。重复进行这样两趟的排序直到数组全部有序。
    奇偶排序实际上在多处理器环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一对都可以用不同的处理器比较和交换，这样可以快速地排序。

偶想不明它这个“重复两趟扫描”有什么用，不就是把奇偶项分别排序了么？怎么会“重复进行这样两趟的排序直到数组全部有序”呢？
偶百度了一下，也没找到相关的文章
麻烦哪位高手指点一下，谢谢！

julines

a[j]和a[j+1]，j是奇数(j＝1，3，5，…)。如果它们的关键字的值次序颠倒，就交换它们。

这句话说了，不是比较a1,a3,a5，而是这样成对比较:a1,a2 a3,a4  a5,a6

julines

没说清楚

奇数扫描就是这样比较
a1,a2
a3,a4
a5,a6
偶数扫描就是这样成对比较：
a2,a3
a4,a5
a6,a7

wgfxman

1、分成奇偶2次，就是为了能够让2个处理器能够尽量平分工作量
2、不管是奇、偶位置的排序，都是跟相邻的数据比较，好像相当于冒泡排序~

呵呵。。具体对应的算法忘了

wgfxman

如果3个处理器，应该也可以分成
3n、3n+1、3n+2这样3轮比较了。。~-~

天魔狂舞

假定有6个成员：
10  7  3  4  9  2
odd num taxis:
7  10  3  4  2  9
even num taxis:
7  3  10  2  4  9
Cyc 2:
3  7  2  10  4  9
3  2  7  4  10  9
Cyc 3:
2  3  4  7  9  10
over!
takes three cycs to compare with the array.

wgfxman

不过，我倒是怀疑 2个处理器处理过程中是不是存在冲突问题~。。

wenbinjiao

“处理器可以分别同时处理每一个奇数对”
这个是指在处理的时候，不同的处理器处理两对不同的数对，比如：
有两个处理器，处理10个数字a(1-10)
-------------------------------------------
第一次比较奇数对
CPU1 处理
a1,a2
a5,a6
a9,a10

CPU2处理
a3,a4
a7,a8
-------------------------------------------
第二次，处理偶数对
CPU1处理
a2,a3
a6,a7

CPU2处理
a4,a5
a8,a9
-------------------------------------------

不存在一个CPU处理奇数，另一个处理偶数的情况

9z本人lz

谢谢