函式概述
qsort 為quick sort的簡寫，意為快速排序，主要用于對各種陣列的排序，在頭檔案stdlib.h中，
因為陣列的元素可能是任何型別的，甚至是結構或者聯合，所以必須高數函式qsort如何確定兩個陣列元素哪一個“更小”，這就需要我們給出比較的規則，即什么算大，什么算小，
通過撰寫比較函式可以為函式qsort提供這些資訊，當給定兩個指向陣列元素的指標p和q時，比較函式必須回傳一個整數，如果*p小于*q,那么回傳的數為負數;如果*p等于*q,那么回傳0.如果*p大于*q,回傳正數，
函式原型
void qsort(void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *))
函式描述
函式的形式引數從左到右分別為：
指向要排序陣列的第一個元素的指標base（如果只是要對陣列的一段區域進行排序，那么要是base指向這段區域的第一個元素，）在一般情況下，base就是陣列的名字；
nmemb是要排序元素的數量（不一定是陣列中元素的數量）；
size是每個陣列元素的大小，用位元組來衡量；
compar為指向比較函式的指標，
比較函式的實作
比較函式的實作是qsort函式能否正確實作的重點，
撰寫比較函式并沒有想象中的那么容易，函式qsort要求它的形式引數型別為void *，但我們不能通過void *型的指標訪問陣列的成員；我們需要指向要比較元素的型別的指標，為了解決這個問題，我們將在比較函式內部把p與q賦給相應對應型別的指標變數，由于常量指標不能賦值給變數，所以在宣告對應指標變數時應該加上const關鍵字，
下面是一個比較整型陣列的比較函式的例子，
int compare(const void *p, const void *q)
{
const int *p1 = p;
const int *q1 = q;
if (*p1 < *q1)
return -1;
else if (*p1 == *q1)
return 0;
else
return 1;
}
當然除了把用const指標變數的方法，還可以使用強制型別轉換的方式來達到這個目的，
int compare(const void *p,const void *q)
{
if(*(int *)p<*(int *)q)
return -1;
else if(*(int *)p==*(int *)q)
return 0;
else
return 1;
}
還可以進一步精簡
int compare(const void *p,const void *q)
{
return *(int *)p-*(int *)q;
}
需要注意的點：比較元素是指標的比較函式的實作，
如果待比較的元素是指標（雖然我們一般不會比較指標的大小，但是我們經常需要對指標代表的空間比較大小，比如比較一個字串陣列的大小，每個字串都由一個指標代表），那么比較函式的實作就比較麻煩了，
首先我們需要明確的是，比較函式中的兩個指標必須要指向需要比較的兩個元素，如果這兩個元素是指標而不是一個物體，那么這兩個指標應該是指向指標的指標，
這里我們以一個比較字串的比較函式舉例：
int compare(const void *p,const void *q)
{
return strcmp(*(char **)p,*(char **)q);
}
9/25補充
昨天刷題的時候發現一個和qsort有關的坑，
如果在寫cmp函式時使用return *(int *)p-*(int *)q;簡寫，而比較函式比較后回傳的是一個int值，這種寫法在比較元素是整型的時候沒有什么問題，但是如果比較的元素是double時，那么回傳值可能和實際值不一樣了，例如如果兩個實型資料分別是1.1和1.0，回傳的結果會變成0，這時函式qsort會把它們當成相同的元素，
此時正確的寫法應該是return *(double *)p>*(double *)q?1:0;，
參考博客：qsort函式排序各種型別的資料，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/103662.html
標籤：C++
上一篇：最好的重試是指數后退和抖動