迪蘭帝的聊天室

一直以來想到排序，我大部份都是使用 Bubble sort 來做排序，並不是最好的，也不是最快的，但是很直觀。 其實在 ANSI C 的標準函式庫裡面就自帶了一個更快、更高接的內建排序函式:Quick Sort 這裡簡介一下 Quick Sort 演算法：

快速排序使用（Divide and conquer）策略來把一個（list）分為兩個（sub-lists）。
步驟為：

1. 從數列中挑出一個元素，稱為 "基準"（pivot），
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
3. 遞迴地（recursive）把小於基准值元素的子數列和大於基准值元素的子數列排序。

運用Quick Sort 的演算法，時間複雜度在最差狀況，有O(n^2) ，但是這樣的狀況並不常見，平均狀況則有O(n log n)的效率。


ANSI C 的標準函式庫裡有一個直接好用的函數，可以直接做快速排序，我們可以使用以下的作法來達成：

qsort( 需要排序的陣列 , 陣列的大小, sizeof(排序的物件), 比較的方法 );

這個函數需要傳入我們需要排序的陣列，陣列裡面的東西不論是什麼，只要能夠排序都可以傳給這個函數，不論是英文字、整數、浮點數、甚至中文字，都可以送進去給他排序蠻神奇的東西。

比較需要注意的是，我們要在函數的最後傳入一個如何比較的方法給 qsort ，畢竟什麼都可以排序的原因是，如何比較大小的規則是由我們程式設計師自行定義，例如我最近寫到的排大小的程式，程式碼如下：

qsort(student, counter, sizeof(int), cmp);


int cmp( const void *a, const void *b) {
    return *((int*) a) - *((int*) b) ;
}

上面這個排序方法是為了將一組學生的陣列進行排序，比較大小的方法用自訂函式 cmp 來定義，而 cmp 裡面我們可以看到傳入的參數是用 void * 這個無型別指標來進行指向，因為就像上面所說，qsort 這個函數可以對任何類型的函數來進行排序，所以他必須要能對任何東西進行指向才可以，但是 return 的時候，我們必須能進行大小的比較，所以我們必須把 void * 轉換成我們原來資料的類型，像是上面我就是轉換成 int * 但是為了要進行大小的操控，所以又必須把指標轉換回原資料，所以在最外層要再包上另外一個 * ，最後用相減的方式，可以知道 a 和 b 之間的大小差別，從而可以進行大小的排序。

結論：
這個方法在程式語言比賽的時候是一個很實用的功能，但是對於新手來說可能不是那麼適合使用，畢竟多了解各種不同的排序演算法的建立方式，以及應用方式，更能增加對於寫作程式的經驗和想法。