鸟窝

using System;
using System.Collections.Generic;


namespace Com.Colobu.Algorithm.Exchange
{
    /// <summary>
    /// <b>奇偶排序</b>的思路是在数组中重复两趟扫描。
    /// 第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1, 3, 5……)。
    /// 如果它们的关键字的值次序颠倒，就交换它们。
    /// 第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4,6……)。
    /// 重复进行这样两趟的排序直到数组全部有序。
    /// 
    /// 平均时间复杂度:O(n^2)
    /// Stability:Yes
    /// </summary>
    public class OddEvenSortAlgorithm
    {
        public static void OddEvenSort<T>(IList<T> szArray) where T : IComparable
        {
            bool sorted = false;
            while (!sorted)
            {
                sorted = true;
                // odd-even
                for (int i = 1; i < szArray.Count - 1; i += 2)
                {
                    if (szArray[i].CompareTo(szArray[i + 1]) > 0)
                    {
                        Swap(szArray, i, i + 1);
                        sorted = false;
                    }
                }
                // even-odd
                for (int j = 0; j < szArray.Count - 1; j += 2)
                {
                    if (szArray[j].CompareTo(szArray[j + 1]) > 0)
                    {
                        Swap(szArray, j, j + 1);
                        sorted = false;
                    }
                }
            }
        }
        private static void Swap<T>(IList<T> szArray, int i, int j)
        {
            T tmp = szArray[i];
            szArray[i] = szArray[j];
            szArray[j] = tmp;
        }
    }
}