你真的理解C語言qsort函數(shù)嗎?帶你深度剖析qsort函數(shù)
一、前言
我們初識C語言時，會做過讓一個整型數(shù)組按照從小到大來排序的問題，我們使用的是冒泡排序法，但是如果我們想要比較其他類型怎么辦呢，顯然我們當(dāng)時的代碼只適用于簡單的整形排序，對于結(jié)構(gòu)體等沒辦法排序，本篇將引入一個庫函數(shù)來實(shí)現(xiàn)我們希望的順序。
二、簡單冒泡排序法
#include <stdio.h>
int main()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int i = 0;
int sz = sizeof(arr);
for (i = 0; i < sz-1; i++)
{
int j = 0;
for (j = 0; j < sz-1-i; j++)
{
int tep = 0;
if (arr[j] > arr[j + 1])
{
tep = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tep;
}
}
}
return 0;
}這是我們最初學(xué)習(xí)的冒泡排序法，我們?nèi)绻哑湫薷囊幌?，能不能比較其它類型的數(shù)據(jù)呢，結(jié)果是肯定的。
三、qsort函數(shù)的使用
1、qsort函數(shù)的介紹
圖片1為整體描述，下面的圖片2、3、4、5、6為圖片1的解釋。
首先我們可以看出qsort函數(shù)不需要返回類型，有四個參數(shù)，分別為空指針、無符號型、無符號型、函數(shù)指針。圖二說明該函數(shù)無返回類型。圖三說明我們base為要排序中的起始地址，是一個空指針類型，所以我們傳首元素地址。圖四說明num為元素個數(shù)，是一個無符號整型，所以我們傳一個無符號整型。圖五說明width為每個元素的寬度，單位為字節(jié)，是一個無符號整型，所以我們傳一個無符號整型。圖六說明這個函數(shù)指針指向一個含有兩個空指針作為參數(shù)并且返回類型為int的（比較）函數(shù)。這個是qsort的最后一個參數(shù)，作用是讓我們提供比較大小的規(guī)則，所以我們傳的時候需要傳一個函數(shù)地址讓庫函數(shù)中qsort的函數(shù)指針來接收。補(bǔ)充：qsort對應(yīng)的頭文件為<stdlib.h>。（比較）函數(shù)中的兩個參數(shù)如果第一個大返回一個大于0的數(shù)，如果第二個大返回一個小于0的數(shù)，如果相等則返回0。
看完這些，相信你對qsort函數(shù)有了初步了解。
2、qsort函數(shù)的運(yùn)用
在這里我們舉出兩個例子來直觀看出qsort的應(yīng)用方法，分別為整型數(shù)組排序和結(jié)構(gòu)體排序。
2.1、qsort函數(shù)排序整型數(shù)組
#include<stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int main()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,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]);
}
這樣就完成了排序。
疑問：
1.qsort第四個參數(shù)（函數(shù)地址）為什么不需要傳參？
首先：我們要知道，我們第四個參數(shù)傳的是一個函數(shù)地址（函數(shù)名加不加取地址符號都可以表示函數(shù)的地址），而不是一個函數(shù)，所以就沒有傳參這個說法。其次：等到庫函數(shù)qsort用函數(shù)指針接收后會進(jìn)行傳參等工作（這是程序內(nèi)部進(jìn)行的，我們不需要管）。
2.為什么函數(shù)定義里面的參數(shù)是空指針類型，而不是特定類型？
因?yàn)閝sort函數(shù)并不知道你要傳的是什么類型，也就是它使用這個函數(shù)時不知道傳什么類型的實(shí)參，所以統(tǒng)一先傳一個空類型地址然后函數(shù)用空類型指針接收。
3.空指針是什么意思，怎么用？
空指針就像一個垃圾桶，我們可以對其賦上任意類型的指針，這很方便，但是它不能直接使用，就像我們賦的時候一樣，用的時候它并不知道你是什么類型，它相當(dāng)于只儲存了一個字節(jié)的地址，沒有明確的步長（指針+1跳過的字節(jié)）和訪問權(quán)限大小（解引用指針訪問的字節(jié)個數(shù)）。所以當(dāng)我們用空指針時，需要進(jìn)行強(qiáng)制類型轉(zhuǎn)換，轉(zhuǎn)換成我們需要的類型。
4.為什么com_int函數(shù)在用的時候要把參數(shù)強(qiáng)轉(zhuǎn)為int？
因?yàn)楫?dāng)我們使用qsort函數(shù)時，我們肯定知道要進(jìn)行排序的類型，所以我們需要根據(jù)自己的需要的類型來寫出對應(yīng)的函數(shù)讓qsort函數(shù)調(diào)用。
2.2、qsort函數(shù)排序結(jié)構(gòu)體
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stu
{
char name[10];
int age;
};
//排序結(jié)構(gòu)體年齡的回調(diào)函數(shù)
int cmp_struct_stu_age(const void*e1,const void*e2)
{
return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
//排序結(jié)構(gòu)體姓名的回調(diào)函數(shù)
int cmp_struct_stu_name(const void* e1, const void* e2)
{
return strcmp(((struct stu*)e1)->name, ((struct stu*)e1)->name);
}
//運(yùn)用qsort函數(shù)排序結(jié)構(gòu)體年齡
void test1()
{
struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
//運(yùn)用qsort函數(shù)排序結(jié)構(gòu)體名字
void test2()
{
struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
}
int main()
{
test1();
//test2();
return 0;
}
補(bǔ)充：
字符串比較大小使用strcmp函數(shù)，對應(yīng)的頭文件為<string.h>，依次從左到右比較字母的ASCII值直到不相等，左邊大返回大于0的數(shù)，右邊大返回小于0的數(shù)，直到最后都相等返回0，如果你仔細(xì)看了最前面關(guān)于qsort的介紹，你會發(fā)現(xiàn)他們很相似，qsort中用到的回調(diào)函數(shù)也是需要返回這樣的形式。
四、利用冒泡排序模擬實(shí)現(xiàn)qsort函數(shù)
你對于qsort內(nèi)部如何執(zhí)行操作的是否感興趣呢？你對于qsort中傳的那些參數(shù)是否存在疑問，不知道他們有什么作用呢，接著看下面的內(nèi)容，讓我們更進(jìn)一步理解qsort的工作原理，同時讓你的冒泡排序變得具有普遍性。
首先我們先試著用my_qsort函數(shù)模擬出qsort函數(shù)來對一個整型數(shù)組排序。
#include <stdio.h>
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void swap(char* buf1, char* buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++, buf1++, buf2++)
{
char tep = 0;
tep = *buf1;
*buf1 = *buf2;
*buf2 = tep;
}
}
void my_qsort(const void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
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);
}
}
}
void test3()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
}
int main()
{
test3();
return 0;
}以上代碼就是我們模擬出的qsort函數(shù)，相信看完這個你會對qsort理解更深刻，不過有一點(diǎn)需要注意，我們模擬時使用的是冒泡排序，而qsort其實(shí)內(nèi)部使用的是快排，所以其實(shí)稍有差距。但大體是一致的。
補(bǔ)充：
1.在my_qsort函數(shù)中，我們在比較函數(shù)（cmp）中傳入的是內(nèi)容解釋：
??(char*)base+jwidth 這個實(shí)際上就是原始的base是空指針類型，所以我們無法直接使用，但我們也不確定傳來的具體是什么類型，因此我們先將其強(qiáng)制類型轉(zhuǎn)換為char，然后根據(jù)指針加幾就跳過幾個步長個字節(jié)來確定每次跳過一個元素。
2.在my_qsort函數(shù)中，我們的swap函數(shù)也是一個重要部分，它是如何實(shí)現(xiàn)的呢？
??首先和1剛開始一樣，我們傳的實(shí)參的形式就是為了保證每次可以跳過一個元素，然后當(dāng)傳到swap函數(shù)里后，我們不像cmp函數(shù)一樣有提前準(zhǔn)備好的強(qiáng)轉(zhuǎn)類型，因此我們需要用一種特別的方法保證可以互換元素，那么我們會想到元素是怎樣儲存的呢，是以二進(jìn)制以字節(jié)為單位儲存的，那么我們?nèi)绻枰粨Q元素，是不是只需要把每個字節(jié)都交換一次就好了呢？答案是肯定的，于是我們也將傳來的地址強(qiáng)制類型轉(zhuǎn)換為char*，保證每次交換的是一個字節(jié)，然后又有一個問題就是我們需要交換幾次呢，還記得之前傳的那個參數(shù)width嗎，它是每個元素的寬度，單位是字節(jié)，因此我們可以通過一個for循環(huán)，修女換width次來使得一個元素所占的字節(jié)全部交換。
我們這一部分雖然是用模擬的qsort來排序整型數(shù)組，但其實(shí)如果這個學(xué)會了的話，結(jié)構(gòu)體和前面說的是一模一樣的，因?yàn)槟M的qsort不用變，只需要改一下cmp函數(shù)的類型即可。
完整代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//排序整型數(shù)組順序時的回調(diào)函數(shù)
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
//聲明結(jié)構(gòu)體類型
struct stu
{
char name[10];
int age;
};
//排序結(jié)構(gòu)體年齡順序時的回調(diào)函數(shù)
int cmp_struct_stu_age(const void*e1,const void*e2)
{
return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
//排序結(jié)構(gòu)體名字順序時的回調(diào)函數(shù)
int cmp_struct_stu_name(const void* e1, const void* e2)
{
return strcmp(((struct stu*)e1)->name, ((struct stu*)e1)->name);
}
//運(yùn)用qsort函數(shù)排序整型數(shù)組
void test1()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
}
//運(yùn)用qsort函數(shù)排序結(jié)構(gòu)體
void test2()
{
struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
//qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
//模擬qsort中的交換函數(shù)
void swap(char* buf1, char* buf2, int width)
{
int i = 0;
for (i = 0; i < width; i++, buf1++, buf2++)
{
char tep = 0;
tep = *buf1;
*buf1 = *buf2;
*buf2 = tep;
}
}
//模擬qsort
void my_qsort(const void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
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);
}
}
}
//運(yùn)用模擬qsort函數(shù)(my_qsort)排序整型數(shù)組
void test3()
{
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
int i = 0;
for (i = 0; i < sz; i++)
printf("%d ", arr[i]);
}
//運(yùn)用模擬qsort函數(shù)(my_qsort)排序結(jié)構(gòu)體
void test4()
{
struct stu s[3] = { {"xiaoming",30},{"lihua",60},{"wangli",40} };
int sz = sizeof(s) / sizeof(s[0]);
my_qsort(s, sz, sizeof(s[0]), cmp_struct_stu_name);
//qsort(s, sz, sizeof(s[0]), cmp_struct_stu_age);
}
int main()
{
//test1(); //用qsort實(shí)現(xiàn)整型數(shù)組排序
//test2(); //用qsort實(shí)現(xiàn)結(jié)構(gòu)體排序
test3(); //用模擬qsort函數(shù)實(shí)現(xiàn)整型數(shù)組排序
//test(4) //用模擬qsort函數(shù)實(shí)現(xiàn)結(jié)構(gòu)體排序
return 0;
}回調(diào)函數(shù)：回調(diào)函數(shù)就是一個通過函數(shù)指針調(diào)用的函數(shù)。如果你把函數(shù)指針（地址）作為參數(shù)傳遞給另一個函數(shù)，當(dāng)這個指針被用來調(diào)用其所指向的函數(shù)時，我們就說這是回調(diào)函數(shù)?；卣{(diào)函數(shù)不是由該函數(shù)的實(shí)現(xiàn)方直接調(diào)用，而是在特定的事件或條件發(fā)生時由另外一方調(diào)用的，用于對該事件或條件進(jìn)行響應(yīng)。
通常來講就是：把這個函數(shù)地址作為參數(shù)傳過去，另一個函數(shù)用函數(shù)指針接收然后再調(diào)用這個函數(shù)，那么這個被調(diào)用的函數(shù)就叫回調(diào)函數(shù)。（通過函數(shù)指針調(diào)用的這個函數(shù)，叫做回調(diào)函數(shù)）
五、總結(jié)
到此這篇關(guān)于你真的理解C語言qsort函數(shù)嗎帶你深度剖析qsort函數(shù)的文章就介紹到這了,更多相關(guān)c語言qsort函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了Qt使用QPainter繪制3D立方體，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-08-08
遞歸法求最大公約數(shù)和最小公倍數(shù)的實(shí)現(xiàn)代碼
今天整理了一下用遞歸法求最大公約數(shù)(gcd)和最小公倍數(shù)(lcm)。主要的工作是求最大公約數(shù)。數(shù)學(xué)上可以用輾轉(zhuǎn)法求最大公約數(shù)2013-05-05
這篇文章主要介紹了C++基礎(chǔ)——類繼承中方法重載，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
以下是對C字符串與C++中string的區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-09-09
這篇文章主要給大家介紹了關(guān)于利用C語言玩轉(zhuǎn)魔方陣的相關(guān)資料,文中詳細(xì)介紹了關(guān)于奇數(shù)魔方陣和4N 魔方陣的實(shí)現(xiàn)方法，通過示例代碼讓大家更好的參考學(xué)習(xí)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11
C語言中變量與其內(nèi)存地址對應(yīng)的入門知識簡單講解
這篇文章主要介紹了C語言中變量與其內(nèi)存地址對應(yīng)的入門知識簡單講解,同時這也是掌握指針部分知識的基礎(chǔ),需要的朋友可以參考下2015-12-12
這篇文章主要為大家介紹了C語言二叉堆，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
插入排序的基本思想是每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。下面我們來詳細(xì)探討下C++實(shí)現(xiàn)插入排序2017-05-05
本文主要介紹了C++ sleep()和usleep()的區(qū)別，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
c++ dynamic_cast與static_cast使用方法示例
本文用示例講解了dynamic_cast、static_cast子類與基類之間轉(zhuǎn)換功能的使用方法2013-11-11