学步园

类别：排序-交换排序
参看 维基百科的定义

Gnome sort
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. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots and is described on Dick Grune's Gnome sort page.

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