C/C++中有一個(gè)快速排序的標(biāo)準(zhǔn)庫函數(shù) qsort ，在stdlib.h和cstdlib 中聲明种玛，其原型為：
void qsort(void *base, int nelem, unsigned int width, int ( * pfCompare)( const void *, const void *));
使用該函數(shù)尔当，可以對(duì)任何類型的一維數(shù)組排序配喳。
-
base是待排序數(shù)組的起始地址； -
nelem是待排序數(shù)組的元素個(gè)數(shù); -
width是待排序數(shù)組的每個(gè)元素的大凶寤础（以字節(jié)為單位）; -
pfCompare是一個(gè)函數(shù)指針辫红，它指向一個(gè)“比較函數(shù)”凭涂。
排序就是一個(gè)不斷比較并交換位置的過程。qsort如何在連元素的類型是什么都不知道的情況下贴妻，比較兩個(gè)元素并判斷哪個(gè)應(yīng)該在前呢切油？
答案是：qsort函數(shù)在執(zhí)行期間，會(huì)通過pfCompare指針調(diào)用一個(gè) “比較函數(shù)”名惩，用以判斷兩個(gè)元素哪個(gè)更應(yīng)該排在前面白翻。這個(gè)“比較函數(shù)”不是C/C++的庫函數(shù)，而是由使用qsort 的程序員編寫的绢片。在調(diào)用qsort時(shí), 將“比較函數(shù)”的名字作為實(shí)參傳遞給pfCompare滤馍。程序員當(dāng)然清楚該按什么規(guī)則決定哪個(gè)元素應(yīng)該在前，哪個(gè)元素應(yīng)該在后底循，這個(gè)規(guī)則就體現(xiàn)在“比較函數(shù)”中巢株。
qsort 函數(shù)的用法規(guī)定，“比較函數(shù)”的原型應(yīng)是：int 函數(shù)名(const void * elem1, const void * elem2);該函數(shù)的兩個(gè)參數(shù)熙涤，elem1 和elem2阁苞，分別指向待比較的兩個(gè)元素。也就是說祠挫， * elem1 和* elem2 就是待比較的兩個(gè)元素那槽。該函數(shù)必須具有以下行為：
- 如果
* elem1應(yīng)該排在* elem2前面，則函數(shù)返回值是負(fù)整數(shù)（任何負(fù)整數(shù)都行）; - 如果
* elem1和* elem2哪個(gè)排在前面都行等舔，那么函數(shù)返回0; - 如果
* elem1應(yīng)該排在* elem2后面骚灸，則函數(shù)返回值是正整數(shù)（任何正整數(shù)都行）。
例如：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int compare(const void *a, const void *b)
{
int *pa = (int*)a;
int *pb = (int*)b;
return (*pa )- (*pb); //從小到大排序
}
void main()
{
int a[10] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
qsort(a, 10, sizeof(int), compare);
for (int i = 0; i < 10; i++)
cout << a[i] << " " << endl;
}
再如：
下面的程序慌植，功能是調(diào)用qsort 庫函數(shù)甚牲，將一個(gè)unsigned int 數(shù)組按照個(gè)位數(shù)從小到大進(jìn)行排序。比如 8蝶柿，23丈钙，15 三個(gè)數(shù)，按個(gè)位數(shù)從小到大排序交汤，就應(yīng)該是 23雏赦，15，8：
#include <stdio.h>
#include <stdlib.h>
int MyCompare( const void * elem1, const void * elem2
{
unsigned int * p1, * p2;
p1 = (unsigned int *) elem1; //語句6
p2 = (unsigned int *) elem2; //語句7
return (* p1 % 10) - (* p2 % 10 ); //語句8
}
#define NUM 5
int main()
{
unsigned int an[NUM] = { 8,123,11,10,4 };
qsort( an, NUM, sizeof(unsigned int), MyCompare);
for( int i = 0;i < NUM; i ++ )
printf("%d ", an[i]);
return 0;
}
上面程序的輸出結(jié)果是：
10 11 123 4 8
qsort 函數(shù)執(zhí)行期間芙扎，需要比較兩個(gè)元素哪個(gè)應(yīng)在前面時(shí)星岗，就以兩個(gè)元素的地址作為參數(shù)，調(diào)用 MyCompare 函數(shù)纵顾。如果返回值小于0伍茄，則qsort 就得知第一個(gè)元素應(yīng)該在前栋盹，如果返回值大于0施逾，則第一個(gè)元素應(yīng)該在后敷矫。如果返回值等于0，則哪個(gè)在前都行汉额。
對(duì)語句6 解釋如下：由于elem1 是 const void * 類型的曹仗，是void 指針，那么表達(dá)式*elem1是沒有意義的蠕搜。elem1 應(yīng)指向待比較的元素怎茫，即一個(gè)unsigned int 類型的變量，所以要經(jīng)過強(qiáng)制類型轉(zhuǎn)換妓灌，將elem1 里存放的地址賦值給 p1轨蛤，這樣，* p1 就是待比較的第一個(gè)元素了虫埂。語句7 同理祥山。語句8 體現(xiàn)了排序的規(guī)則。如果 *p1 的個(gè)位數(shù)小于 *p2 的個(gè)位數(shù)掉伏，那么就返回負(fù)值缝呕。其他兩種情況不再贅述。
轉(zhuǎn)載鏈接：https://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html
