奇偶排序基本資訊

一個奇偶排序或磚排序是一個簡單的排序演算法，這是與本地互連並行處理器使用而開發的。它通過比較列表中所有奇數/偶數索引的相鄰元素對來工作，如果一對錯誤的順序，則切換元素。對於偶數/奇數索引對，下一步重複此步驟。然後它在奇數/偶數和偶數/奇數步之間交替，直到列表被排序。

Odd-Even 排序的虛擬碼：

if n>2 then
    1. apply odd-even merge(n/2) recursively to the even subsequence a0, a2, ..., an-2 and to the odd subsequence a1, a3, , ..., an-1
    2. comparison [i : i+1] for all i element {1, 3, 5, 7, ..., n-3}
else
    comparison [0 : 1]

維基百科有 Odd-Even 排序的最好例證：

https://i.stack.imgur.com/FVktW.gif

奇偶排序示例：

https://i.stack.imgur.com/LZJKu.jpg

執行：

我用 C#語言實現奇偶排序演算法。

public class OddEvenSort
{
    private static void SortOddEven(int[] input, int n)
    {
        var sort = false;

        while (!sort)
        {
            sort = true;
            for (var i = 1; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
            for (var i = 0; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortOddEven(input, input.Length);
        return input;
    }
}

輔助空間： O(n)
時間複雜度： O(n)