奇偶排序

维基百科,自由的百科全书
跳转至: 导航搜索
奇偶排序
Odd even sort animation.gif
使用奇偶排序法对一列随机数字进行排序的过程
分類 排序算法
數據結構 数组
最差時間複雜度 \Theta(n^2)


奇偶排序,或奇偶换位排序,或砖排序[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;
        }
    }
}

参考文献[编辑]

  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. MillerFranz L. Alt and Marshall C. Yovits, ., Parallel Sorting Algorithms, 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.