Definição e significado de 奇偶排序

奇偶排序

使用奇偶排序法对一列随机数字进行排序的过程
分類	排序算法
數據結構	数组
最差時間復雜度
最佳算法	不
查 · 論 · 編

奇偶排序，或奇偶换位排序，或砖排序^[1]，是一种相对简单的排序算法，最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。

该算法中，通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶-奇）位置数字对。如此交替进行下去。

  处理器数组的排序

在并行计算排序中，每个处理器对应处理一个值，并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作，交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。^[2]

该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分割算法中，每个处理器在每一步对自己所拥有的子数组进行排序，然后与邻居执行合并分割或换位合并。^[3]

  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;
        }
    }
}

  参考文献

查 · 論 · 編 排序算法 理論 計算複雜性理論 | 大O符號 | 全序關係 | 列表 | 穩定性 | 比較排序 | 拓扑排序 | 排序網絡 交換排序法 冒泡排序 | 鸡尾酒排序 | 奇偶排序 | 梳排序 | 侏儒排序 | 快速排序 |臭皮匠算法 | Bogo排序 選擇排序法 选择排序 | 堆排序 | Smooth排序 | 笛卡尔树排序 | 锦标赛排序 | 循环排序 插入排序法 插入排序 | 希尔排序 | 二叉查找树排序 | 图书馆排序 | Patience排序 归并排序法 归并排序 | 多相归并排序 | Strand排序 分布排序法 美国旗帜排序 | 珠排序 | 桶排序 | 爆炸排序 | 计数排序 | 鸽巢排序 | 相邻图排序 | 基数排序 | 闪电排序 混合排序法 Tim排序 | 内省排序 | Spread排序 | 反移排序 | J排序 其他 双调排序器 | Batcher归并网络 | 两两排序网络