原文地址：C語言標準庫函數(shù)qsort那點小事

????????qsort包含在<stdlib.h>頭文件中，此函數(shù)根據(jù)你給的比較條件進行快速排序，通過指針移動實現(xiàn)排序。排序之后的結(jié)果仍然放在原數(shù)組中。使用qsort函數(shù)必須自己寫一個比較函數(shù)。

函數(shù)原型：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

函數(shù)一共四個參數(shù)，沒返回值。一個典型的qsort的寫法如下:

void qsort(s,n,sizeof(s[0]),cmp);

????????其中第一個參數(shù)是參與排序的數(shù)組名（或者也可以理解成開始排序的地址，因為可以寫&s[i]，這個問題下面有說明）；第二個參數(shù)是參與排序的元素個數(shù)； 第三個參數(shù)是單個元素的大小（推薦使用sizeof(s[0])這樣的表達式，下面也有說明）；第四個參數(shù)就是很多人覺得非常困惑的比較函數(shù)，關(guān)于這個函數(shù),還要說的比較麻煩...

下面來討論cmp這個比較函數(shù)（寫成cmp是我的個人喜好,你可以隨便寫成什么，比如qcmp什么的）。典型的cmp的定義是:

int cmp(const void *a,const void *b);

????????返回值必須是int，兩個參數(shù)的類型必須都是const void *，那個a,b是我隨便寫的兩個參數(shù)。?假設(shè)是對int排序的話，如果是升序，那么就是如果a比b大返回一個正值，小則負值，相等返回0，后面有例子來說明對不同的類型如何進行排序。

在函數(shù)體內(nèi)要對a，b進行強制類型轉(zhuǎn)換后才能得到正確的返回值，不同的類型有不同的處理方法。具體情況請參考后面的例子。

**** 關(guān)于快排的一些小問題 ****

1、快排是不穩(wěn)定的，這個不穩(wěn)定一個表現(xiàn)在其使用的時間是不確定的，最好情況(O(n))和最壞情況(O(n^2))差距太大，我們一般說的O(nlog(n))都是指的是其平均時間。

2、快排是不穩(wěn)定的，這個不穩(wěn)定表現(xiàn)在如果相同的比較元素，可能順序不一樣，假設(shè)我們有這樣一個序列,3,3,3,但是這三個3是有區(qū)別的，我們標記為3a,3b,3c,快排后的結(jié)果不一定就是3a,3b,3c這樣的排列，所以在某些特定場合我們要用結(jié)構(gòu)體來使其穩(wěn)定（No.6的例子就是說明這個問題的）。

3、快排的比較函數(shù)的兩個參數(shù)必須都是const void *的,這個要特別注意，寫a和b只是我的個人喜好，寫成cmp也只是我的個人喜好。推薦在cmp里面重新定義兩個指針來強制類型轉(zhuǎn)換，?特別是在對結(jié)構(gòu)體進行排序的時候。

4、快排qsort的第三個參數(shù)，那個sizeof，推薦是使用sizeof(s[0])這樣，特別是對結(jié)構(gòu)體，往往自己定義2*sizeof(int)這樣的會出問題，用sizeof(s[0)既方便又保險。

5、如果要對數(shù)組進行部分排序，比如對一個s[n]的數(shù)組排列其從s[i]開始的m個元素，只需要在第一個和第二個參數(shù)上進行一些修改:

void qsort(&s[i],m,sizeof(s[i]),cmp);