qsort() 簡介 qsort()是一個內建於<stdlib.h>的函數 他會利用快速排序法(Quick Sort)，幫你在O(nlgn)[代表計算次數跟nlgn成正比] 的時間內排序，既快速又正確(如果你寫對了XD)。 qsort()定義 void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) ); qsort()要做的事情 基本上qsort()要做的事情可以視為在一段記憶體上，有num個各占size bytes記憶體的 東西(一個int，連續幾個int，一個字串...)，你要依照comparator的規則，將他們排序。 qsort()需要的東西 1.void* base ==> 起始指標 這是要排序的那段記憶體的第一個位置的指標， 也可以視為第一個要排序的東西的指標。 這邊需要特別注意，這邊丟進去的，是一個指標，而不是一整個陣列喔！ 2.size_t num ==> 東西個數 這是代表你有num個東西要排序 3.size_t size ==> 每個東西所佔用記憶體(以byte計) 現在qsort()知道了一開始的指標，以及你有多少個東西需要排序 但是他不知道每一個東西到底用了多少記憶體，如果你用的是一個int， 那就是4bytes，如果你用了三個int，那就是12bytes... 如此一來，qsort()就可以很清楚的知道，記憶體的某一段到某一段就是某一個元素的位置 ，也才有辦法做出比較、排序的動作。 4.int ( *comparator ) ( const void*, const void* ) ==> 比較函數 這裡是一個qsort()內的函數指標，也是排序中最核心的部分 在排序的過程中，qsort()會多次呼叫這個函數，每次會丟入兩個東西的指標 而這個函數的任務就是判斷這兩個東西的優先順位，假如說丟入兩個東西a、b 如果a的順位在b前面，就輸出一個負數；如果b的順位在前面，就輸出一個正數 而順位相同的情況則輸出0。 5.呼叫 qsort() 這裡有個需要注意的地方，比較函數的部分 不是qsort(...,...,...,(*comparator)(const void *,const void *)); 函數指標的欄位，必須要引入你自己寫的比較函數，例如： qsort(... , ... , ... , cmp); 這指標... 對你沒看錯，這些指標的型態，都是void*的型態，為什麼不是int*呢？ 原來，qsort()不只能夠排序int的東西，還有很多很多型態的東西，qsort()都能夠將他們 排序，但是每種型態佔用的記憶體都不一樣呀，所以像int*的ptr+1與double*的ptr+1就會 指向不同的記憶體，所以qsort()為了避免這樣的情況，在宣告的時候預設都為void* (void*每個1byte)，需要比較、計算時，再讓使用者轉型成正在使用的型態。 所以比較函數怎麼辦... 按照qsort()函數指標，我會有需要寫一個比較函數是長下面這樣子的 int cmp(const void* a,const void* b){ ... } 啊哈!!那我只要依照a,b他們優先順位來輸出負數、零、正數就好了嘛!! 不過等等，a是void的指標...那*a不就是void嗎?! 那我要怎麼去比較啊!! 所以這時候就要做另外一件事情：指標轉型 把void的指標轉型成int的指標(或是你想要的東西的指標) 這樣，加*取值回來就會是你要的形態了！ 給個範例：由小到大排序 int cmp( const void* a, const void* a ){ int* A = (int*) a;//將原本為void*的a轉型為int*並指定給A int* B = (int*) b; if( *A < *B ) return -1; //若*A比*B小，代表A的順位比較前面 else if( *A == *B ) return 0; else return 1; return 0; } ... qsort( array, n, sizeof(int), cmp ); ... 差不多到這裡，qsort()也介紹完了，接下來講幾個大家比較常遇到的問題： 1.東西的大小塞錯 假如說要對座標int array[100000][3]作排序， 應該是要qsort( array, n ,sizeof(int)*3 ,cmp); 或是qsort( array, n ,sizeof(array[0]) ,cmp);才對。 2.到底比較函數丟進來的指標是指到哪裡？ 如果函數的引數沒有打錯，丟進來的指標應該是指到某一個東西最前面的指標 假如說丟進來的a是目前在第k格的指標，那a應該就會指到array[k][0]的位置，也就是說 a+1就是array[k][1]的位置，a+2就是array[k][2]的位置，所以三種願望，一個指標就 讓你滿足了。 3.真的呼叫完這個qsort()，他就排好了嗎?! 真的！ 最後補個八卦 你開燈了對吧wwwww -- Google 時の音の精靈| ████████▕検索▏検索オプション | 表示設定 ▇▇ ￣￣￣￣￣￣￣ ￣￣￣￣ 搜尋： ⊙ウェブ全体から検索 ○日本語のページを検索 ○蘿莉検索 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.192.77.105 ※ 編輯: hallogameboy 來自: 140.112.4.234 (10/28 14:41)