// 一、冒泡排序(Bubble)???



namespace ?BubbleSorter
{
???? public ? class ?BubbleSorter
???? {
???????? public ? void ?Sort( int []?list)
???????? {
???????????? int ?i,?j,?temp;
???????????? bool ?done? = ? false ;
????????????j? = ? 1 ;
???????????? while ?((j? < ?list.Length)? && ?( ! done))
???????????? {
????????????????done? = ? true ;
???????????????? for ?(i? = ? 0 ;?i? < ?list.Length? - ?j;?i ++ )
???????????????? {
???????????????????? if ?(list[i]? > ?list[i? + ? 1 ])
???????????????????? {
????????????????????????done? = ? false ;
????????????????????????temp? = ?list[i];
????????????????????????list[i]? = ?list[i? + ? 1 ];
????????????????????????list[i? + ? 1 ]? = ?temp;
????????????????????}
????????????????}
????????????????j ++ ;
????????????}
????????}
????}

???? public ? class ?MainClass
???? {
???????? public ? static ? void ?Main1()
???????? {
???????????? int []?iArrary? = ? new ? int []? {? 1 ,? 5 ,? 13 ,? 6 ,? 10 ,? 55 ,? 99 ,? 2 ,? 87 ,? 12 ,? 34 ,? 75 ,? 33 ,? 47 ?} ;
????????????BubbleSorter?sh? = ? new ?BubbleSorter();
????????????sh.Sort(iArrary);
???????????? for ?( int ?m? = ? 0 ;?m? < ?iArrary.Length;?m ++ )
????????????????Console.Write( " {0}? " ,?iArrary[m]);
????????????Console.WriteLine();
????????}
????}
} ???
??
// 二、選擇排序(Selection)???



namespace ?SelectionSorter
{
???? public ? class ?SelectionSorter
???? {
???????? private ? int ?min;
???????? public ? void ?Sort( int []?list)
???????? {
???????????? for ?( int ?i? = ? 0 ;?i? < ?list.Length? - ? 1 ;?i ++ )
???????????? {
????????????????min? = ?i;
???????????????? for ?( int ?j? = ?i? + ? 1 ;?j? < ?list.Length;?j ++ )
???????????????? {
???????????????????? if ?(list[j]? < ?list[min])
????????????????????????min? = ?j;
????????????????}
???????????????? int ?t? = ?list[min];
????????????????list[min]? = ?list[i];
????????????????list[i]? = ?t;
????????????}
????????}
????}

???? public ? class ?MainClass2
???? {
???????? public ? static ? void ?Main2()
???????? {
???????????? int []?iArrary? = ? new ? int []? {? 1 ,? 5 ,? 3 ,? 6 ,? 10 ,? 55 ,? 9 ,? 2 ,? 87 ,? 12 ,? 34 ,? 75 ,? 33 ,? 47 ?} ;
????????????SelectionSorter?ss? = ? new ?SelectionSorter();
????????????ss.Sort(iArrary);
???????????? for ?( int ?m? = ? 0 ;?m? < ?iArrary.Length;?m ++ )
????????????????Console.Write( " {0}? " ,?iArrary[m]);
????????????Console.WriteLine();
????????}
????}
} ???
??
// 三、插入排序(InsertionSorter)???



namespace ?InsertionSorter
{
???? public ? class ?InsertionSorter
???? {
???????? public ? void ?Sort( int []?list)
???????? {
???????????
???????????? for ?( int ?i? = ? 1 ;?i? < ?list.Length;?i ++ )
???????????? {
???????????????? int ?t? = ?list[i];
???????????????? int ?j? = ?i;
???????????????? // 依次往前推。
???????????????? // 先是前兩個元素。
???????????????? // 然后是前三個元素。
???????????????? // 然后是前N個元素。
???????????????? while ?((j? > ? 0 )? && ?(list[j? - ? 1 ]? > ?t))
???????????????? {
????????????????????list[j]? = ?list[j? - ? 1 ];
???????????????????? -- j;
????????????????}
????????????????list[j]? = ?t;
????????????}
????????}
????}

???? public ? class ?MainClass3
???? {
???????? public ? static ? void ?Main3()
???????? {
???????????? int []?iArrary? = ? new ? int []? {? 1 ,? 13 ,? 3 ,? 6 ,? 10 ,? 55 ,? 98 ,? 2 ,? 87 ,? 12 ,? 34 ,? 75 ,? 33 ,? 47 ?} ;
????????????InsertionSorter?ii? = ? new ?InsertionSorter();
????????????ii.Sort(iArrary);
???????????? for ?( int ?m? = ? 0 ;?m? < ?iArrary.Length;?m ++ )
????????????????Console.WriteLine( " {0} " ,?iArrary[m]);
????????????Console.WriteLine();
????????}
????}
} ???
?? /**/ /*
???*?有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據。

void??insertSort(Type*?arr,long?len)?//InsertSort?algorithm
{
???????long?i=0,j=0;//iterator?value
???????Type?tmpData;
???????assertF(arr!=NULL,"In?InsertSort?sort,arr?is?NULL\n");
???????for(i=1;i<len;i++)
???????{
??????????????j=i;
??????????????tmpData=arr;
??????????????while(tmpData<arr[j-1]&&j>0)
??????????????{
?????????????????????arr[j]=arr[j-1];
?????????????????????j--;
??????????????}
??????????????arr[j]=tmpData;
???????}
}
插入排序算法思路是:
假定這個數組的序是排好的,然后從頭往后,如果有數比當前外層元素的值大,則將這個數的位置往后挪,直到當前外層元素的值大于或等于它前面的位置為止.這具算法在排完前k個數之后,可以保證a[1…k]是局部有序的,保證了插入過程的正確性.

??? */
// 四、希爾排序(ShellSorter)???



namespace ?ShellSorter
{
???? public ? class ?ShellSorter
???? {
???????? public ? void ?Sort( int []?list)
???????? {
???????????? int ?inc;
???????????? for ?(inc? = ? 1 ;?inc? <= ?list.Length? / ? 9 ;?inc? = ? 3 ? * ?inc? + ? 1 )?;
????????????Console.WriteLine( " {0}--- " ,inc);

???????????? for ?(;?inc? > ? 0 ;?inc? /= ? 3 )
???????????? {
????????????????Console.WriteLine( " {0}?around " ,?inc);
???????????????? for ?( int ?i? = ?inc? + ? 1 ;?i? <= ?list.Length;?i? += ?inc)
???????????????? {
???????????????????? // inc?是間隔
???????????????????? // j?是每幾個元素，1為開始坐標
???????????????????? int ?t? = ?list[i? - ? 1 ]; // “被比較的數”的元素放到?t?中
???????????????????? int ?j? = ?i;????????????????????
???????????????????? while ?((j? > ?inc)? && ?(list[j? - ?inc? - ? 1 ]? > ?t))
???????????????????? { // 因為要比較的數(前面的數)大于“被比較的數”
????????????????????????list[j? - ? 1 ]? = ?list[j? - ?inc? - ? 1 ];
????????????????????????j? -= ?inc; // 移動比較元素
????????????????????}
????????????????????list[j? - ? 1 ]? = ?t; // 最后把?t?放在比較范圍的每個位置
????????????????}
????????????}
????????}
????}

???? public ? class ?MainClass4
???? {
???????? public ? static ? void ?Main4()
???????? { // ??????????????????????????????0??1??2???3??4??5
???????????? int []?iArrary? = ? new ? int []? {? 15 ,? 5 ,? 13 ,? 6 ,? 10 ,? 55 ,? 99 ,? 2 ,? 87 ,? 12 ,? 34 ,? 75 ,? 33 ,? 47 ?} ;
????????????ShellSorter?sh? = ? new ?ShellSorter();
????????????sh.Sort(iArrary);
???????????? for ?( int ?m? = ? 0 ;?m? < ?iArrary.Length;?m ++ )
????????????????Console.WriteLine( " {0}? " ,?iArrary[m]);
????????????Console.WriteLine();
????????}
????}
}



/**/ /* 希爾排序(縮小增量法)?
屬于插入類排序,是將整個無序列分割成若干小的子序列分別進行插入排序??
排序過程：先取一個正整數d1<n，把所有序號相隔d1的數組元素放一組，
?*?組內進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；
?*?直至di=1，即所有記錄放進一個組中排序為止???
????
??初始：d＝5???
??????????49???38???65???97???76???13???27???49*???55???04???
???????????|----------------------------|???
???????????????38??????????????????????????????27???
???????????????????|---------------------------|???
????????????????????????65??????????????????????????????49*???????
?????????????????????????|----------------------------|???
????????????????????????????????97??????????????????????????????55???
??????????????????????????????????|--------------------------|???
??????????????????????????????????????76????????????????????????????????04
????????????????????????????????????????|-----------------------------|?
??一趟結果???
??????????13???27???49*?55???04???49???38???65?????97?????76??
??d=3
??????????13???27???49*?55???04???49???38???65?????97?????76??
?????????????|---------------|----------------|--------------------|???
??????????????????27????????????????04?????????????????65???
???????????????????|----------------|----------------|???
?????????????????????????49*???????????????49??????????????????97???
???????????????????????????|----------------|-----------------|???
??二趟結果???
????????????13???04???49*?38???27???49???66???65???97???76???
??d=1???
????????????13???04???49*?38???27???49???66???65???97???76???
??????????????|-----|-----|-----|-----|-----|-----|-----|-----|-----|
??三趟結果???
????????????04???13???27???38???49*?49???55???65???76???97????
*/