奇偶排序

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

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

处理器数组的排序

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

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

Batcher奇偶归并排序

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

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

程序代码

C语言

void odd_even_sort(int arr[], int len) {
    int odd_even, i;
    int temp;
    int sorted = 0;
    while (!sorted) {
        sorted = 1;
        for (odd_even = 0; odd_even < 2; odd_even++)
            for (i = odd_even; i < len - 1; i += 2)
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    sorted = 0;
                }
    }
}

C++

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void odd_even_sort(T arr[], int len) {
    int odd_even, i;
    bool sorted = false;
    while (!sorted) {
        sorted = true;
        for (odd_even = 0; odd_even < 2; odd_even++)
            for (i = odd_even; i < len - 1; i += 2)
                if (arr[i] > arr[i + 1]) {
                    swap(arr[i], arr[i + 1]);
                    sorted = false;
                }
    }
}

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

Array.prototype.odd_even_sort = function() {
    var odd_even, i;
    var temp;
    var sorted = 0;
    while (!sorted) {
        sorted = 1;
        for ( odd_even = 0; odd_even < 2; odd_even++)
            for ( i = odd_even; i < this.length - 1; i += 2)
                if (this[i] > this[i + 1]) {
                    temp = this[i];
                    this[i] = this[i + 1];
                    this[i + 1] = temp;
                    sorted = 0;
                }
    }
    return this;
};

PHP

function swap(&$x, &$y) {
    $t = $x;
    $x = $y;
    $y = $t;
}
function odd_even_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
    $sorted = 0;
    while (!$sorted) {
        $sorted = 1;
        for ($odd_even = 0; $odd_even < 2; $odd_even++)
            for ($i = $odd_even; $i < count($arr) - 1; $i += 2)
                if ($arr[$i] > $arr[$i + 1]) {
                    swap($arr[$i], $arr[$i + 1]);
                    $sorted = 0;
                }
    }
}

原文地址:https://zh.wikipedia.org/wiki/%E5%A5%87%E5%81%B6%E6%8E%92%E5%BA%8F

知识共享 署名-相同方式共享 3.0协议之条款下提供

文章作者: 张拓
文章链接: http://www.xssl.online/%e5%a5%87%e5%81%b6%e6%8e%92%e5%ba%8f/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自 张拓的博客
浏览次数: 589

张拓

陕西西安蓝田张拓QQ1070410059。一生所求不过“心安”二字。 然,尘世多纷扰。

发表回复