奇偶排序又叫砖排序，是一种相对简单的算法，最初发明用于有本地互联的并行计算。在具有多处理器的环境中很有用，处理器可以分别处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一刻都可以用不同的处理器并行处理比较和交换，实现高速排序。
算法思想
- 选取所有的奇数列的元素，与其右边的相邻元素进行比较，将较小的元素排序在前面
- 选取所有的偶数列的元素，与其右边的相邻元素进行比较，将较小的元素排序在前面
- 重复前面的步骤，直到所有的序列有序为止
代码实现
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)
- 是一个稳定的算法
注意：
- 因为我们可以覆盖所有的元素，才能对全体元素进行排序，如果待排序的元素不能形成连续的链状结构，被分成了两部分或更多，这样多个元素之间不能交流，信息被隔断，就无从排序了
- 奇偶排序还用于Batchar并行排序网络中，这个后面会介绍，它采用了比较-交换和完美洗牌操作
动态过程
odd-even sort.gif
