Posted by : Dylandy Chang 2012年10月26日 星期五

一直以來想到排序,我大部份都是使用 Bubble sort 來做排序,並不是最好的,也不是最快的,但是很直觀。 其實在 ANSI C 的標準函式庫裡面就自帶了一個更快、更高接的內建排序函式:Quick Sort 這裡簡介一下 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 * 但是為了要進行大小的操控,所以又必須把指標轉換回原資料,所以在最外層要再包上另外一個 * ,最後用相減的方式,可以知道 ab 之間的大小差別,從而可以進行大小的排序。

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

Leave a Reply

Subscribe to Posts | Subscribe to Comments

技術提供:Blogger.

- Copyright © 迪蘭帝的聊天室 -Metrominimalist- Powered by Blogger - Designed by Johanes Djogan -