C語言庫函數(shù)qsort及bsearch快速排序算法使用解析
qsort
qsrot 就是C語言庫函數(shù)中的快速排序函數(shù),對數(shù)組,結(jié)構體都可以實現(xiàn)快速排序, 他在頭文件<stdlib.h>中使用,聲明格式為:
void qsort(void* base, size_t nums, size_t size, int (*compare)(const void *, const void*))
這么煩人一長串的參數(shù)各是什么意思呢,base 是指向要排序的數(shù)組的第一個元素的指針。nums是由 base 指向的數(shù)組中元素的個數(shù)。size 是數(shù)組中每個元素的大小,以字節(jié)為單位。compare 是用來比較兩個元素的函數(shù),這個比較函數(shù)需要我們自己補全。
含義
void*代表著任意類型的數(shù)組,這個數(shù)組也就是我們想用來排序的對象數(shù)組;size_t 在系統(tǒng)里面被定義成 int 類型的,所以我們可以把 size_t修飾的數(shù)默認為一個整數(shù)。
為什么要細化出數(shù)組大小和元素大???這和我排序有毛關系?其實這是為了區(qū)分不同類型的數(shù)組,int 和 char 類型的數(shù)組每個元素所占空間就不一樣,自然要區(qū)別開。
int main() { int arr[6] = { 1,4,5,8,2,3}; qsort(arr, 6, sizeof(arr[0]), compare); }
最后的 compare 函數(shù)我是直接將這個元素作為參數(shù)傳進來,那么問題來了,這個比較函數(shù)怎么寫?
我們根本不用管那個 *compare 的指針什么鬼,他就相當于告訴你這里在用一個外部函數(shù),我們只要明白整個函數(shù)名兒上去就是妥妥的了,這個函數(shù)名不一定就叫 compare ,諸君自便。
實現(xiàn)
后面的(const void , const void)自然就是這個函數(shù)的參數(shù)了,兩個 void* 實際運用的時候就看成 a ,b,既然是外部函數(shù)我們就要自己動手了,我們的最終目的是為了排序,比較函數(shù)就應該實現(xiàn)數(shù)組元素大小的比較,本質(zhì)上說就是在比較 a和b 的大小,而a,b是我數(shù)組中任意的兩兩元素。
那首先要做的就是把這個不知道什么類型的 void 指針變成我們給定的,之前代碼中給的是整型數(shù)組,這里就要對應變成整型指針,這兩個指針指向數(shù)組中的兩個整數(shù),既然要比較,我們就直接做減法看正負即可,把這兩個指針轉(zhuǎn)換成真正的整數(shù)后就大功告成了:
int* p = (int*)a; int* q = (int*)b; int c = *p; int d = *q;
成品如下:
#include<stdlib.h> int compare(const void* a,const void* b) { int* p = (int*)a; int* q = (int*)b; int c = *p; int d = *q; return c - d; } int main() { int i = 0; int arr[6] = { 1,4,5,8,2,3 }; qsort(arr, 6, sizeof(arr[0]), compare); for (i = 0; i < 6; i++) { printf("%d ", arr[i]); } return 0; }
結(jié)果如下
結(jié)構體的排序也是同理,如下:
#include<stdlib.h> int compare(const void* a,const void* b) { int* p = (int*)a; int* q = (int*)b; int c = *p; int d = *q; return c - d; } int main() { int i = 0; int arr[6] = { 1,4,5,8,2,3 }; qsort(arr, 6, sizeof(arr[0]), compare); for (i = 0; i < 6; i++) { printf("%d ", arr[i]); } return 0; }
結(jié)果就是根據(jù)結(jié)構體中 a 成員大小來排的:
格局打開
1.上面是實現(xiàn)從小到大排列,要實現(xiàn)從大到小排只需 return d - c 即可。
2.如果是比較浮點數(shù),注意在兩個數(shù)相差不大時,介于(-1,1),因為現(xiàn)在是整型指針,返回值也是整型,return 回來的就是個 0,造成無意義操作,怎么處理呢?很簡單,改成如下即可:
int compare(const void* a,const void* b) { int* p = (int*)a; int* q = (int*)b; int c = *p; int d = *q; if(c - d<0) { return -1; } else { return 1; } }
bsearch
bsearch (binary search)也是C語言庫函數(shù),功能是執(zhí)行二分查找,聲明定義如下
void *bsearch(const void *key, const void *base, size_t nums, size_t size, int (*compar)(const void *, const void *))
和 qsort 一樣是又臭又長,且隨我慢慢看,key 是指向要查找的元素的指針,類型轉(zhuǎn)換為 void*,其他的和 qsort 里的是一樣的不再贅述。
強調(diào)一下,bsearch()的使用有一個硬性要求,這個數(shù)組必須要有順序性,從大到小或從小到大否則達咩,所以建議和 qsort 配套實驗更佳。
這個 key 就是我們的查找目標,void* 代表著一個指針,所以我們在函數(shù)里面是不能直接給出的 key 的值,那我們就取他對應的地址就行
int key = 5; bsearch(&key,arr,6,sizeof(int),compare1);
接下來順水推舟驗證一下:
judge = (int*) bsearch (&key, values, 5, sizeof (int), cmpfunc); if( judge != NULL ) { printf("find %d is true\n", *judge); } else { printf("%d can not be found\n", *judge); } return(0); }
整個代碼如下:
#include<stdlib.h> int compare(const void* a, const void* b) { int* p = (int*)a; int* q = (int*)b; int c = *p; int d = *q; return c - d; } int compare1(const void* key, const void* a) { return (*(int*)key-*(int*)a); } int main() { int* judge; int arr[6] = { 1,4,5,8,2,3 }; qsort(arr, 6, sizeof(arr[0]), compare); int key = 5; judge = (int*)bsearch(&key, arr, 5, sizeof(int), compare1); if (judge != NULL) { printf("find %d is true\n", *judge); } else { printf("%d can not be found\n", *judge); } return(0); }
今天就先到這里吧,摸了家人們,更多關于C語言庫函數(shù)qsort及bsearch快速排序算法的資料請關注腳本之家其它相關文章!
相關文章
C語言 解決不用+、-、×、÷數(shù)字運算符做加法的實現(xiàn)方法
本篇文章是對在C語言中解決不用+、-、×、÷數(shù)字運算符做加法的方法進行了詳細的分析介紹,需要的朋友參考下2013-05-05C語言數(shù)組實現(xiàn)公交車管理系統(tǒng)
這篇文章主要介紹了C語言數(shù)組實現(xiàn)公交車管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-12-12C++ Qt實現(xiàn)瀏覽器網(wǎng)頁內(nèi)嵌的音視頻播放器
這篇文章主要為大家詳細介紹了如何利用C++ Qt實現(xiàn)瀏覽器網(wǎng)頁內(nèi)嵌的音視頻播放器,并支持軟硬解碼,支持音頻,支持錄像截圖,支持多路播放等,感興趣的可以了解下2024-01-01基于c++11的event-driven library的理解
這篇文章主要介紹了基于c++11的event-driven library的理解,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-02-02Qt+QListWidget實現(xiàn)氣泡聊天界面(附源碼)
由于最近的項目需要,做了些相關IM的工作。所以聊天框也是必不可少的一部分。本文以QListWidget+QPainter繪制的Item做了一個Demo。該Demo只是做一個示例,感興趣的可以了解一下2022-12-12