引入
我們在學(xué)習(xí)排序的時候，第一個接觸到的應(yīng)該都是冒泡排序，我們先來復(fù)習(xí)一下冒泡排序的代碼，來作為一個鋪墊和引入。
代碼如下：
#include<stdio.h>
void bubble_sort(int *arr, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
很簡單的一種排序方法，但我們可以發(fā)現(xiàn)一個問題，那就是冒泡排序不夠通用，它只能用于整型數(shù)組的排序，如果我要排序float類型，或者排序結(jié)構(gòu)體要怎么辦呢。
下面，我們就來介紹一個比較萬能的排序函數(shù)，qsort函數(shù)
簡介
先來簡單了解一下qsort函數(shù)的各個部分
語法格式
它的固定格式如下：
int cmp_int(const void* e1, const void* e2)
{
}
注意：他的格式是固定的，比如返回值類型必須是int類型，形參的類型也是固定的，只有返回值的部分是自己編寫的，也就是說，當(dāng)返回值類型不是int的時候，我們需要進行強制類型轉(zhuǎn)換或者手動將其返回值改成int類型
（這在下文會詳細(xì)說明）
參數(shù)解釋
在調(diào)用函數(shù)時，傳參格式如下：
void qsort(void* base,
size_t num,
size_t width,
int (*cmp)(const void* e1, const* e2)
);
可以看一下這張圖，里面講解了qsort函數(shù)的各個參數(shù)分別表示的是什么，
base:起始位置,待排序數(shù)組的首元素地址 num：數(shù)組的大小，單位是元素，待排序數(shù)組的元素個數(shù)
width：元素大小，單位是字節(jié)，待排序數(shù)組的單個元素的大小 cmp：函數(shù)指針（比較函數(shù)：compare
function），比較兩個元素的函數(shù)的地址
解釋：對于不同類型元素的比較的方法是不同的，此處就是將兩個元素的比較方法寫成函數(shù)，傳到qsort函數(shù)中，然后使用指針cmp進行調(diào)用
e1和e2可以簡單地認(rèn)為是要比較的兩個元素的地址，（下面會做補充說明）
對void *的解釋
先拋出一個問題：下面這個代碼有什么問題
int main()
{
int a = 0;
int *pa = &a;
char* pc = &a;
return 0;
}
問題就是：第四行和第五行：此處雖然可以存儲，但會報警告：從“int *”
到“char *”的類型不兼容。
那么，我們這時就可以使用，void *（無指針類型）來解決這個問題
void* p = &a;
//void *類型的指針可以接收任意類型的地址
此處就可以很好地解釋qsort函數(shù)的第一個參數(shù)：void* base
補充：
對于void *類型的指針無法進行解引用
因為不知道進行解引用之后，要訪問幾個字節(jié)
同理，也無法進行無符號型的指針與整數(shù)的運算
那么，在qsort函數(shù)中，如何比較e1與e2呢
可以將二者強制轉(zhuǎn)換成所需的類型（代碼中會提到這一點）
返回值
下圖是英文版的介紹
對qsort函數(shù)返回值的解釋
當(dāng)e1<e2,返回值小于0
當(dāng)e1=e2，返回值等于0
當(dāng)e1>e2 返回值大于0
提示：所以可以利用這個規(guī)律將不是int類型的返回值手動變成int型（下文float類型那里會詳細(xì)說明）
使用
此處我們舉三個例子，分別是int、float和結(jié)構(gòu)體類型變量的比較
int類型
明確需要
我們需要三個函數(shù)：main函數(shù)（調(diào)用test函數(shù)），test函數(shù)（調(diào)用qsort函數(shù)、打印最終結(jié)果），和cmp_int函數(shù)（提供元素的比較方法）
test函數(shù)
1.創(chuàng)建數(shù)組
2.計算大小
3.調(diào)用qsort函數(shù)
4.打印最終結(jié)果
cmp_int函數(shù)
照著前面的固定格式，然后返回值那里就直接用
（這里我一寫*，他就識別成斜體，大家直接看下面的代碼吧…)
最終代碼
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void test1()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
test1();
return 0;
}
還是比較好理解的，就不做過多解釋了
float類型
對于cmp_float函數(shù)的說明
問題
我們知道cmp_float函數(shù)的返回值必須是int類型的，但,
*(float*)e1 - *(float*)e2
的返回類型是float類型，在運行時會報一個警告：return”: 從“float”轉(zhuǎn)換到“int”，可能丟失數(shù)據(jù)，
此處提供兩種解決方法：
1.使用if else語句手動判斷大小并根據(jù)情況分別返回一個負(fù)數(shù)、0、一個正數(shù)
代碼如下：
if (*(float*)e1 > *(float*)e2)
{
return 1;
}
else if (*(float*)e1 == *(float*)e2)
{
return 0;
}
else
{
return -1;
}
2.使用強制類型轉(zhuǎn)換，轉(zhuǎn)換成int類型
最終代碼
#include<stdlib.h>
int cmp_float(const void* e1, const void* e2)
{
return *(float*)e1 - *(float*)e2;
}
void test2()
{
float f[] = { 9.0, 8.0, 7.0, 6.0 ,5.0 ,4.0 ,3.0, 2.0, 1.0 };
int sz = sizeof(f) / sizeof(f[0]);
qsort(f, sz, sizeof(f[0]), cmp_float);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%.3f ", f[i]);
}
}
int main()
{
test2();
return 0;
}
結(jié)構(gòu)體類型
如果我們想要排序結(jié)構(gòu)體類型的變量，那就很有意思了，我們一步一步來分析
明確需要
main函數(shù)、test3函數(shù)、cmp_stu函數(shù)
下面我們重點解釋一下test3函數(shù)和cmp_stu函數(shù)
test3函數(shù)
1.創(chuàng)建結(jié)構(gòu)體類型的數(shù)組，并初始化
2.求數(shù)組元素個數(shù)
3.調(diào)用qsort函數(shù)，里面包含了cmp_stu函數(shù)的地址，即調(diào)用cmp_stu函數(shù)
cmp_stu函數(shù)
照貓畫虎
我們按照前面的兩個例子寫出來的應(yīng)該是
int cmp_struct(const void* e1, const void* e2)
{
return *(struct*)e1 - *(struct*)e2;
}
但這么寫是錯誤的， 因為結(jié)構(gòu)體是復(fù)雜對象，無法直接用 > 或 < 進行比較，那么我們就需要確定是用哪個成員去作為比較的標(biāo)準(zhǔn)
再通過->來訪問相應(yīng)的成員
下面給出兩個例子，此處分別以年齡age作為排序標(biāo)準(zhǔn)和以名字name來排序，
cmp_stu_by_age函數(shù)
將e1和e2從void* 類型轉(zhuǎn)換成結(jié)構(gòu)體類型指針，然后再通過->訪問相應(yīng)的成員
然后直接讓二者相減即可，此處在強制類型轉(zhuǎn)換時別忘了寫上struct就行
int cmp_stu_by_age(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
這個函數(shù)的實現(xiàn)還是與cmp_int函數(shù)有一些相似的，
cmp_stu_by_name函數(shù)
提示：此處比較的是字符串，同樣不能用 > < 來進行比較
而是要用strcmp函數(shù)進行比較，包含頭文件<string.h>
int cmp_stu_by_name(const void* e1, const void* e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
最終代碼
#include<stdlib.h>
struct Stu
{
char name[40];
int age;
};
int cmp_stu_by_age(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int cmp_stu_by_name(const void* e1, const void* e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
提示，此處比較的是字符串，同樣不能用 > < 來進行比較
而是要用strcmp函數(shù)進行比較
}
void test3()
{
struct Stu s[3] = { {"zhang", 20},{"li", 30},{"wang", 40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{
test3();
return 0;
}
三個例子到這里就介紹結(jié)束了，其實這樣看下來也不是很難理解。
下面我們來學(xué)習(xí)qsort函數(shù)的模擬實現(xiàn)，也就是優(yōu)化bubble_sort函數(shù)，使它能排序任意類型的元素
模擬實現(xiàn)
引入：
此處提出一個問題：如果說，我不想使用qsort函數(shù)，我就想使用冒泡函數(shù)，那我要如何改進它，才能達(dá)到和qsort函數(shù)相同的效果呢？
函數(shù)調(diào)用方面的改進
接收地址
如果說想讓冒泡排序函數(shù)具有排序任意類型元素的功能，那么首先，它就應(yīng)該能接收任意類型元素的地址（類似于qsort中的base參數(shù)）
元素個數(shù)
函數(shù)需要知道要排序多少個元素，所以就需要傳入數(shù)組的大小（類似num參數(shù)）
元素大?。▽挾龋?/h4>
知道了待排序數(shù)組的起始位置和元素個數(shù)后，我們需要對數(shù)組中的元素進行移動操作， 那么我們就需要知道元素的大小是什么
簡易版框架如下：
void bubble_sort(void* base, int sz, int width)
{
int i = 0;//次數(shù)
for (i = 0; i < sz; i++)
{
//每次需要比較的元素對數(shù)
int j = 0;
for (j = 0; j < sz - 1 - i; j++)//比較兩個元素
{
}
}
}
疑問1：
基本框架搭建好了，那我們要如何比較兩個元素呢，我們又不知道他們的類型？
所以我們在傳參的時候，還需要將兩個元素的比較方法（函數(shù)）一并傳進bubble_sort函數(shù)中，也就是第四個參數(shù)
首先，要傳入的肯定是函數(shù)的地址，
其次，我們需要返回一個值來告訴我們比較的結(jié)果是什么（此處類似qsort函數(shù)的返回值）
最后，對于要比較的兩個元素，因為要求函數(shù)具有通用性，所以參數(shù)類型就是void *類型
代碼如下：
void bubble_sort(void* base, int sz, int width, int(*cmp)(void* e1,void* e2) )
{
int i = 0;//次數(shù)
for (i = 0; i < sz; i++)
{
//每次需要比較的元素對數(shù)
int j = 0;
for (j = 0; j < sz - 1 - i; j++)//比較兩個元素
{
if(cmp()>0)//交換if(cmp()>0)//交換
{
}
}
}
}
}
疑問2：if語句
if(cmp()>0)//交換
{
}
我們知道這個語句是比較兩個元素，那我們怎么找到這倆個元素呢？
我們知道，base就是首元素的地址，
想法1
那么有人想通過加減整數(shù)來找到后面的元素，這個問題在我前面的文章提到過：因為元素是void*類型的，不知道元素大小，無法與整數(shù)進行運算
想法2
那么又有人想：將base傳換成（int*）類型再運算不就行了嗎，
還是不對，因為我們不知道傳進來的參數(shù)究竟是什么類型，所以我們不能假定他的類型
想法3
小明這時候提出來：我們已經(jīng)知道了每個元素的大?。簑idth，那可不可以先把base轉(zhuǎn)換成char*類型，再加上每個元素的字節(jié)大小width呢？
這么做就可以了，
因為char*大小是一個字節(jié)，每次移動width個字節(jié)，就進入到下一個元素中了
if語句代碼如下：
if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換
{
}
疑問3：怎么交換
這里先創(chuàng)建一個swap函數(shù)用于兩個元素的交換
void Swap(char*buf1, char*buf2)
{
}
void bubble_sort(void* base, int sz, int width)
{
int i = 0;//次數(shù)
for (i = 0; i < sz; i++)
{
//每次需要比較的元素對數(shù)
int j = 0;
for (j = 0; j < sz - 1 - i; j++)//比較兩個元素
{
if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width);
}
}
}
}
但是，我們仔細(xì)看，Swap函數(shù)接收的參數(shù)類型是char*，一個字節(jié)大小，如果我這個元素是8個字節(jié)類型，要怎么交換呢，
所以如果按照一個字節(jié)一個字節(jié)這么交換的方式，我們就需要知道要交換的元素的字節(jié)大?。╳idth），以及要交換幾次
代碼如下：
void Swap(char*buf1, char*buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
簡單實現(xiàn)（int類型）
完整代碼如下：
void Swap(char*buf1, char*buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void bubble_sort(void* base, int sz, int width, int (*cmp)(void*e1, void*e2))
{
int i = 0;//次數(shù)
for (i = 0; i < sz; i++)
{
//每次需要比較的元素對數(shù)
int j = 0;
for (j = 0; j < sz - 1 - i; j++)//比較兩個元素
{
if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void test4()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
}
int main()
{
test4();
return 0;
}
想要進行其他類型的比較只需要在調(diào)用bubble_sort函數(shù)時，將第四個參數(shù)修改成對應(yīng)的比較方法即可（當(dāng)然，這需要自己構(gòu)建）
小提示：
->的優(yōu)先級高于強制類型轉(zhuǎn)換，所以要用()先將強制類型轉(zhuǎn)換括起來，先轉(zhuǎn)換，再訪問
題外話
因為想要使bubble_sort函數(shù)具有通用性，所以我們需要將不同類型元素的比較方法的函數(shù)的地址傳進來（也就是第四個參數(shù)），而這種將函數(shù)地址傳進另一個函數(shù)，由這個函數(shù)去實現(xiàn)調(diào)用的方法，就稱為回調(diào)函數(shù)（大概就是這個意思），我這幾天在整理指針的知識，有時間就寫一篇博客。
結(jié)語
沒想到感覺沒怎么寫，就寫了六千多字（捂臉）
只能再一次感嘆C的豐富文章來源：http://www.zghlxwxcb.cn/news/detail-652872.html
文章到這里就結(jié)束了，希望這篇文章對你有所幫助，我們下篇文章見~文章來源地址http://www.zghlxwxcb.cn/news/detail-652872.html
到了這里，關(guān)于C語言庫函數(shù)之 qsort 講解、使用及模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
