鸟窝

using System;
using System.Collections.Generic;

namespace Com.Colobu.Algorithm.Exchange
{
    /// <summary>
    /// <b>Comb sort</b> improves on bubble sort, and rivals algorithms like Quicksort. 
    /// The basic idea is to eliminate turtles, or small values near the end of the list, 
    /// since in a bubble sort these slow the sorting down tremendously.
    /// 
    /// 平均时间复杂度:O(nlogn)
    /// Stability:No
    /// </summary>
    public class CombSortAlgorithm
    {
        public static void CombSort<T>(IList<T> szArray) where T : IComparable
        {
            int gap = szArray.Count;
            bool swapped = true;

            while (gap > 1 || swapped)
            {
                if (gap > 1)
                {
                    gap = (int)(gap / 1.25);
                }

                int i = 0;
                swapped = false;
                while (i + gap < szArray.Count)
                {
                    if (szArray[i].CompareTo(szArray[i + gap]) > 0)
                    {
                        T t = szArray[i];
                        szArray[i] = szArray[i + gap];
                        szArray[i + gap] = t;
                        swapped = true;
                    }
                    i++;
                }
            }
        }
    }
}