[計程] qsort()

[hallogameboy (時の音の精靈)]

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
推 DarkAkira:    姜姜好威!!
推 anfranion:    姜姜好威!!          推精美教學文XD
推 sa072686:     姜姜好威!!          我以為八卦是何木木問題XD
推 andy74139:    姜姜好威!!          超精美的!!:)
推 chengweiwei:  姜姜好威!!          精美教學文 我開燈了..y
推 iago2007:     姜姜好威!!          原來有這麼好用的東西
推 robertabcd:   姜姜好威!!          姜姜好威!!
推 davll:        姜姜好威!!          超精美～♥
推 s864372002:   姜姜好威!!          //可以嘗試自己寫sort丟上去喔
推 hoisee:       姜姜好威!!
推 yiping0928:   姜姜好威!!          謝謝姜姜的精美教學文:D
推 TommyKSHS:    姜姜好威!!          感謝超精美的教學文~
推 YAOMMENT:     姜姜好威!!          超感謝姜姜
※ 編輯: hallogameboy    來自: 140.112.4.234        (10/28 14:41)
推 lianngg:      姜姜好威!!          超強!GOOOOOOD
推 rinner:       姜姜好威!!          大感謝~
推 tonylo2ooo:不懂耶= =""我測資都會過可是竟然給我零分@_@~~~~