鸟窝

using System;
using System.Collections.Generic;

namespace Com.Colobu.Algorithm.Exchange
{
    /// <summary>
    /// <b>Gnome sort</b> is a sorting algorithm which is similar to insertion sort, 
    /// except that moving an element to its proper place is accomplished 
    /// by a series of swaps, as in bubble sort. 
    /// Gnome Sort is based on the technique used by the standard Dutch Garden Gnome. 
    /// Here is how a garden gnome sorts a line of flower pots. 
    /// Basically, he looks at the flower pot next to him and the previous one; 
    /// if they are in the right order he steps one pot forward, 
    /// otherwise he swaps them and steps one pot backwards. 
    /// Boundary conditions: if there is no previous pot, 
    /// he steps forwards; if there is no pot next to him, he is done.
    /// 
    /// 平均时间复杂度:O(n^2)
    /// Stability:Yes
    /// </summary>
    public class GnomeSortAlgorithm
    {
        public static void GnomeSort<T>(IList<T> szArray) where T : IComparable
        {
            int i = 1;
            int j = 2;
            int count = szArray.Count;
            while (i < count)
            {
                if (szArray[i - 1].CompareTo(szArray[i]) < 0) //for descending sort, reverse the comparison to >=
                {
                    i = j;
                    j = j + 1;
                }
                else
                {
                    Swap(szArray, i - 1, i);
                    i = i - 1;
                    if (i == 0)
                    {
                        i = j;
                        j = j + 1;
                    }
                }
            }
        }
        private static void Swap<T>(IList<T> szArray, int i, int j)
        {
            T tmp = szArray[i];
            szArray[i] = szArray[j];
            szArray[j] = tmp;
        }
    }
}