# 奇偶排序

分類 使用奇偶排序法对一列随机数字进行排序的过程 排序算法 数组 $\Theta(n^2)$

## Batcher奇偶归并排序

Batcher奇偶归并排序是一种相关但更有效率的排序算法，采用比较-交换和完美-洗牌操作。[4]

Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。[5]

## 算法

Python语言：

```# 假设已有列表a等待排序
while True:
sorted = True
# 处理奇-偶对
for i in xrange(1, len(a)-1, 2):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i] # 交换
sorted = False
# 处理偶-奇对
for i in xrange(0, len(a)-1, 2):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i] # 交换
sorted = False
if sorted:
break
```

JavaScript语言：

```/* 假设已有数组a等待排序*/
var sorted = false;
while(!sorted)
{
sorted=true;
for(var i = 1; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}

for(var i = 0; i < list.length-1; i += 2)
{
if(a[i] > a[i+1])
{
swap(a, i, i+1);
sorted = false;
}
}
}
```

## 参考文献

1. ^ Phillips, Malcolm. Sort Techniques Array Sorting. [3 August 2011].
2. ^ N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
3. ^ S. Lakshmivarahan, S. K. Dhall, and L. L. Miller, Parallel Sorting Algorithms, (编) Franz L. Alt and Marshall C. Yovits, Advances in computers (Academic Press), 1984, 23: 295–351, ISBN 9780120121236
4. ^ Robert Sedgewick. Algorithms in Java, Parts 1-4 3rd. Addison-Wesley Professional. 2003: 454–464. ISBN 9780201361209.
5. ^ Allen Kent and James G. Williams. Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. 1993: 33–38. ISBN 9780824722821.