[教學] (C++/C )Sort (排序法) @ 一個小小工程師的心情抒發天地

這一篇文章主要是介紹Sort，其實Sort是一個很常考的面試題目，而最出名的就是BubbleSort (泡沫排序法)，這東西其實看似簡單，但其實....=_= 真的很簡單...一點也玩不出什麼新花樣 (XD)，主要就是推的時候比較麻煩而已。

在開始前，我想先介紹一下排序( sort )，排序這玩意在很多地方都用得到 (廢話...)，常用的排序大概有七種 :
1.選擇排序 [SelectSort]
2.氣泡排序 [BubbleSort]
3.插入排序 [InsertSort]
4.快速排序 [QuickSort ]
5.歸併排序 [MergeSort ]
6.樹排序 [TreeSort ]
7.堆排序 [HeapSort ]

在這篇文章裡面，我們先挑兩個比較容易的來講解 (1,2)，剩下的其實推起來也算不難，不過要花的時間比較多，我就先不在這一篇文章裡面敘述了，等哪天想到或有空，在補上來 (真的很有求知慾的朋友..在寄信給我吧 )

首先，我們先介紹"選擇排序法" ( Selection Sort ) !，Selection sort 應該是最好理解的一種排序法，我們只需要遵循以下幾個步驟，即可成功。

1. 在第一個數到第N個數裡面，找出最"小"的數
2. 將第一個數和最小的那個數字對調 (這個時候第一個數字就是最小的數字)
3. 接下來再用第二個數到第N個數找出第二小的數字
4. 再將第二個數字和第二小的數字對調
5. 不斷的重複以上的步驟，直到loop到這個Array的到數第二個數字，就可以停了 (因為最後一個一定是最大的)

如果圖片不清楚，可以直接參考這邊

#include <iostream>
using namespace std;

void PrintArray (int nSize, int A[]) ;

void SelectionSort (int nSize , int A[])
{
   int i , j , k , t ;

   for (i = 0 ; i < nSize-1 ; i++)
   {
       for (j = i+1 , k = i ; j<nSize ; j++)
       {
           if (A[j] < A[k])
               k = j ;
       }
       t = A [k] ;
       A[k] = A[i] ;
       A[i] = t ;
   }
}

void PrintArray (int nSize, int A[])
{
   //驗證
   cout << endl;
   for (int i = 0 ; i< nSize ; i++)
   {
       cout <<A[i]<<" " ;
   }
   cout << endl ;
}

int main()
{
int A[] = {6,1,3,2,8} ;

   int nSize = sizeof (A) /sizeof (A[0]) ;

   cout << "Before: " ;
   PrintArray(nSize,A) ;

   SelectionSort(nSize,A) ;

   cout << "After : " ;
   PrintArray(nSize,A);

}

連code都寫出來了，小夥伴們可以拿張紙筆，自己推一下，應該不會很難理解，推個兩次三次基本上就能知道後面會怎樣進行了。

   緊接者我們來介紹第二種排序 BubbleSort ，這個就是最常考的玩意，理解後個人認為難度為 0 ，這也是本人可以不用推算，直接可以很順的默寫出來的排序法，真的很簡單，讓我們來看看使用方法吧 !

1. 先比較

先比較最後兩個數，將比較小的放在前面。
再比較倒數第二、三兩個數，將比較小的放在前面。
反覆這樣的步驟，直到第一、二兩個數，將比較小的放在前面。此時第一個數就是最小的數。

code :

void BubbleSort (int nSize , int A[])
{
int i , j , t ;

   for (i = 0 ; i< nSize-1 ;i++)
   {
       for (j = nSize-1 ; j>i ;j--)
       {
           if (A[j] < A[j-1])
           {
               t       = A[j] ;
               A[j]   = A[j-1] ;
               A[j-1]   = t;

//print
PrintArray(nSize , A) ;

           }
       }
   }
}

void PrintArray (int nSize, int A[])
{
   //驗證
   cout << endl;
   for (int i = 0 ; i< nSize ; i++)
   {
       cout <<A[i]<<" " ;
   }
   cout << endl ;
}

int main()
{
int A[] = {6,1,3,2,8} ;

   int nSize = sizeof (A) /sizeof (A[0]) ;

   cout << "Before: " ;
   PrintArray(nSize,A) ;

   BubbleSort(nSize,A) ;

   cout << "After : " ;
   PrintArray(nSize,A);

}

Result :

/***************************************************************************/

這些都算完之後，讓我們來用一個混合題來驗證剛剛教的東西，到底是真的有吸收進去，還是只是依樣畫葫蘆，知其然而不知其所以然。

題目 : 我現在有一個 Array ，其質為 : int A[] ={1,0,9,8,7,0,2,6,4,0,3,0,5} ;

現在我要做的，並不是由小排到大 (靠..由小排到大的話，上面隨便拉一個套進去就能用了，還考毛啊 )，而是我希望你能夠幫我排出 :

結果為 : 1 2 3 4 5 6 7 8 9 0 0 0 0

只要遇到0，就往後丟，其他的就照順序排好，使用方式不限，不過我們這裡講的是排序法，所以還是希望用排序的方式來解決這個問題。

/*真的解不開的話，請往下拉*/
(答案如下)

void Mixed (int nSize , int A[])
{
int i , j , k , t;

   for (i = 0 ; i <nSize-1 ; i++)
   {
       for (j = i+1 ,k = i ; j<nSize ; j++)
       {
           if (A[j] > A[k] )
               k = j ;
       }
       t = A[k] ;
       A[k] = A[i] ;
       A[i] = t ;
   }

   i =j = k = t = 0;
   cout << "Selection sort finish ! \n" ;
   PrintArray(nSize , A) ;

   for (i = 0 ; i < nSize ; i++)
   {
       for (j = nSize-1 ; j > i ;j-- )
       {
           if (A[i] > A[j] && A[j] != 0)
           {
               t = A[j] ;
               A[j] = A[i] ;
               A[i] = t ;
           }
       }
   }
}

int main()
{
   int A[] ={1,0,9,8,7,0,2,6,4,0,3,0,5} ;
   //int B[] = {8,4,2,6,1,5,7,3,9} ;
   int nSize = sizeof (A) /sizeof (A[0]) ;

   cout << "Selection sort - before : " ;
   PrintArray(nSize,A) ;

   Mixed(nSize,A) ;

   cout << "Selection sort - After : " ;
   PrintArray(nSize,A) ;

}