奇偶排序

奇偶排序又叫砖排序，是一种相对简单的算法，最初发明用于有本地互联的并行计算。在具有多处理器的环境中很有用，处理器可以分别处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一刻都可以用不同的处理器并行处理比较和交换，实现高速排序。

算法思想

1. 选取所有的奇数列的元素，与其右边的相邻元素进行比较，将较小的元素排序在前面
2. 选取所有的偶数列的元素，与其右边的相邻元素进行比较，将较小的元素排序在前面
3. 重复前面的步骤，直到所有的序列有序为止

代码实现

function odd_even(A: list[1..n]){    
     whie has_swap:  
        for i from 0 to n-1 && i%2==0 && i+1<=n-1{  
               if(A[i] > A[i+1])  
                  swap(A[i], A[i+1])  
        }  
        for j from 1 to n-1 && j%2==1 && j+1<=n-1{  
               if(A[j] > A[j+1])  
                   swap(A[j], A[j+1])  
        }  
} 

过程举例

举例：待排数组[6 2 4 1 5 9]
第一次
[6 2 4 1 5 9]   [2 6 1 4 5 9]
第二次
[2 6 1 4 5 9]  [2 1 6 4 5 9]
第三趟
[2 1 6 4 5 9]  [1 2 4 6 5 9]
第四趟
[1 2 4 6 5 9]  [1 2 4 5 6 9]

算法分析

• 这个算法可以并行延伸到每个core处理多个数据的情况上（上面的例子中，每个core只处理一个对，两个数据）
• 最好的情况下时间复杂度为O(n)，参考冒泡，一次搞定
• 最差的情况下，时间复杂度为O(n^2)
• 最差的情况下，时间复杂度为O(n^2)
• 是一个稳定的算法

注意：

1. 因为我们可以覆盖所有的元素，才能对全体元素进行排序，如果待排序的元素不能形成连续的链状结构，被分成了两部分或更多，这样多个元素之间不能交流，信息被隔断，就无从排序了
2. 奇偶排序还用于Batchar并行排序网络中，这个后面会介绍，它采用了比较-交换和完美洗牌操作

动态过程

odd-even sort.gif