C語言中關(guān)于庫函數(shù) qsort 的模擬實(shí)現(xiàn)過程
前言
我們?cè)谏弦黄┛椭v解了庫函數(shù)qsort的使用,今天我為大家?guī)韖sort的模擬實(shí)現(xiàn)。上一篇博客這個(gè)庫函數(shù)的閱讀鏈接:C語言中關(guān)于庫函數(shù) qsort 快排的用法
其實(shí)有人會(huì)問,我明明已經(jīng)掌握了庫函數(shù)qsort的使用方法,為何還要去寫模擬實(shí)現(xiàn),其實(shí)啊,學(xué)好一個(gè)東西,不僅僅只是會(huì)用就可以,如果我們能更深層次的去探索這個(gè)函數(shù)是怎么實(shí)現(xiàn)的,我相信,這其中的樂趣,不一般。。。
僅以此篇文章作為我學(xué)習(xí)的見證,希望能夠各位帶來一定的幫助,謝謝。文章若有不妥之處,歡迎指點(diǎn)。這是一個(gè)共同進(jìn)步的平臺(tái)?。?!
一、qsort函數(shù)
我們先看看qsort函數(shù)的使用:
#include <stdio.h> #include <stdlib.h> int cmp_int(const void* e1, const void* e2) { //e1-e2,得到的是升序 return *(int*)e1 - *(int*)e2; } int main() { int arr[10] = { 2,3,1,4,5,6,7,9,8,10 }; 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]); return 0; }
qsort函數(shù)的四個(gè)參數(shù)我們就不過多講了。大家翻一翻上一篇博客。
二、qsort函數(shù)實(shí)現(xiàn)思路
1. 底層原理
其實(shí)啊,qsort函數(shù),底層原理是 快速排序,只不過我們?cè)谑褂玫臅r(shí)候,被封裝成了函數(shù)而已。我們寫的是從冒泡排序的角度寫。
2. 函數(shù)傳參
qsort(arr, sz, sizeof(arr[0]), cmp_int);
1). 第一個(gè)參數(shù)
傳入的是一個(gè)數(shù)組,可能大多數(shù)人的第一反應(yīng)就是對(duì)應(yīng)函數(shù)的形參用數(shù)組指針來接收,我當(dāng)初自己在寫的時(shí)候,也是這樣想的,當(dāng)我們?cè)酵竺鎸?,發(fā)現(xiàn)這個(gè)形參用數(shù)組指針來接收,并不好用,至于為什么,往下看。
我們?cè)谏弦黄┛吞岬竭^ void* 這個(gè)概念,它能接收來自所有類型的值,我們這第一個(gè)參數(shù)的形參就寫成 void* base。
2). 第二個(gè)參數(shù)
傳入的是元素個(gè)數(shù),我們?cè)偬岬揭粋€(gè)概念:size_t 返回類型,它是一個(gè)無符號(hào)整形(unsigned int),我在《C primer plus》書找到了相關(guān)的解釋,圖放在下面:
因?yàn)槲覀儌鞯诙€(gè)參數(shù)時(shí),傳的其實(shí)就是sizeof的返回值,所有函數(shù)形參部分就寫 size_t sz。
3). 第三個(gè)參數(shù)
這第三個(gè)參數(shù)啊,跟第二個(gè)參數(shù)是一樣的,計(jì)算得到的也是sizeof的返回值,也直接寫size_t width。(代表一個(gè)元素的大?。?/p>
4). 第四個(gè)參數(shù)
這第四個(gè)參數(shù)是一個(gè)函數(shù)啊,我們?cè)趥鲄⒌臅r(shí)候,傳的其實(shí)是這個(gè)函數(shù)的地址啊,在my_sort(就是等會(huì)我們需要實(shí)現(xiàn)的qsort函數(shù)),在my_sort函數(shù)里面,我們通過傳過來的函數(shù)地址(cmp_int)去調(diào)用這個(gè)(cmp_int)函數(shù),我們就叫回調(diào)函數(shù)。這里有點(diǎn)繞,仔細(xì)品。
既然傳過來的是一個(gè)函數(shù)的地址,對(duì)應(yīng)的,我們就用函數(shù)指針去接收,具體的代碼看下面:
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*));
有的小伙伴就會(huì)問函數(shù)指針是是什么?
就是用來接收函數(shù)的地址,用的指針,具體的原理,大家可以去CSDN查,這里,我們就不多講了。
局部代碼:
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*)) { //函數(shù)里面實(shí)則還是冒泡排序 int i = 0; for (i = 0; i < sz; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { //進(jìn)行判斷和交換 } } }
這就是qsort函數(shù)大致的框架,還有一點(diǎn)點(diǎn)小細(xì)節(jié)問題,處理了就完成了,加油哦。
三、局部函數(shù)實(shí)現(xiàn)
現(xiàn)在放在我們面前的問題,怎么進(jìn)行數(shù)值的判斷和交換。
int arr[10]={2,1,4,5,6,3};
我們以這個(gè)數(shù)組為例,我們想想,如果我們要排一個(gè)升序的數(shù)組,只需要我們傳遞給(cmp_int)函數(shù)的兩個(gè)參數(shù)相減為正數(shù),上一篇博客提到了口訣“左減右為升序,反之則降”,即就是e1 - e2 大于0 ,也就是e1>e2了。 注:函數(shù)參數(shù)(const void* e1,const void* e2)
知道了其中原理,就好實(shí)現(xiàn)了唄,if語句判斷,如果(cmp_int)函數(shù)的放回值大于0,我們就交換一下兩個(gè)數(shù)。
void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*)) { //函數(shù)里面實(shí)則還是冒泡排序 int i = 0; for (i = 0; i < sz; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { //進(jìn)行判斷和交換 if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) { //此處函數(shù)傳參的時(shí),并非只需要傳遞兩個(gè)需要交換的數(shù)據(jù),還有數(shù)據(jù)的大小,即就是字節(jié)數(shù) //例如是整體數(shù)據(jù)交換,而Swap函數(shù),其實(shí)函數(shù)里面需要循環(huán)4次才行,因?yàn)槭?個(gè)字節(jié)的數(shù)據(jù)嘛 Exch((char*)base + j * width, (char*)base + (j + 1) * width, width); } } } }
隨著j的增加,我們比較的數(shù)據(jù)也一個(gè)個(gè)的往后移,特別注意(char*) base + j * width,我們?cè)谑褂胋ase時(shí),必須先要進(jìn)行強(qiáng)制類型轉(zhuǎn)換,這樣再進(jìn)行加減操作才可以。因?yàn)?base的類型是 void * 類型,沒有具體的大小。強(qiáng)制類型轉(zhuǎn)換后,再加上j*width個(gè)字節(jié),這樣就能找到數(shù)組中一個(gè)個(gè)的元素。
接下來就是函數(shù)Exch的實(shí)現(xiàn),這個(gè)函數(shù)就是交換兩個(gè)數(shù)的位置用的,(exchange)。上面的if語句如果成立,我們就調(diào)用函數(shù)Exch,去交換兩個(gè)數(shù)的位置,傳參的話,跟if語句里面的參數(shù)一樣的,毋庸置疑。只是我們?cè)趥鲄⒌臅r(shí)候,還需要傳第三個(gè)參數(shù)width,因?yàn)槲覀冋{(diào)用函數(shù)Exch后,函數(shù)里面一次交換,只能交換1個(gè)字節(jié)的內(nèi)容。有小伙伴就會(huì)問,我一次直接交換4個(gè)字節(jié)的內(nèi)容,這不是簡(jiǎn)單的多了嘛。。。。
對(duì)于整形數(shù)組,一次直接交換4個(gè)字節(jié)的內(nèi)容,當(dāng)然簡(jiǎn)單了,但是我們需要交換其他數(shù)據(jù)類型的時(shí)候呢,難道還要重新寫一遍my_sort嗎??是吧,所以,1個(gè)字節(jié)慢慢交換,循環(huán)width次就行,這樣寫出來的函數(shù),才是通用的。
Exch函數(shù)的實(shí)現(xiàn)
void Exch(char* cmp1, char* cmp2, size_t width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *cmp1; *cmp1 = *cmp2; *cmp2 = tmp; cmp1++, cmp2++; //逗號(hào)表達(dá)式,從左到右,依次執(zhí)行 } }
這里面就簡(jiǎn)單多了,就是創(chuàng)建一個(gè)臨時(shí)變量 ,交換數(shù)據(jù)后,對(duì)應(yīng)的地址加1即可,特別注意一下函數(shù)形參部分哦,為什么要寫 char*。值得思考哦。
四、全部代碼匯集
int cmp_int(const void* e1, const void* e2) { return *(int*)e2 - *(int*)e1; } void Exch(char* cmp1, char* cmp2, size_t width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *cmp1; *cmp1 = *cmp2; *cmp2 = tmp; cmp1++, cmp2++; //逗號(hào)表達(dá)式,從左到右,依次執(zhí)行 } } void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*)) { //函數(shù)里面實(shí)則還是冒泡排序 int i = 0; for (i = 0; i < sz; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { //進(jìn)行判斷和交換 if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) { //此處函數(shù)傳參的時(shí),并非只需要傳遞兩個(gè)需要交換的數(shù)據(jù),還有數(shù)據(jù)的大小,即就是字節(jié)數(shù) //例如是整體數(shù)據(jù)交換,而Swap函數(shù),其實(shí)函數(shù)里面需要循環(huán)4次才行,因?yàn)槭?個(gè)字節(jié)的數(shù)據(jù)嘛 Exch((char*)base + j * width, (char*)base + (j + 1) * width, width); } } } } int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; int sz = sizeof(arr) / sizeof(arr[0]); my_sort(arr, sz, sizeof(arr[0]), cmp_int); int i = 0; for (i = 0; i < 10; i++) printf("%d ", arr[i]); return 0; }
五、總結(jié)
簡(jiǎn)單的給大家說了一下整體代碼的思路,還有細(xì)節(jié)問題,沒能給大家表達(dá)清楚,我感到非常遺憾。
特別注意一下冒泡排序里面的邏輯,又特別是里面的if語句,這是整個(gè)代碼的關(guān)鍵,其他的就沒多大的問題,捋清楚了,這些,應(yīng)該就能懂了,還有就是指針哦,雖然有點(diǎn)難,但是始終相信功夫不負(fù)有心人!
如果還有什么不理解的,我們?cè)谠u(píng)論區(qū)聊,共同進(jìn)步。加油??!
下次見?。?!
到此這篇關(guān)于C語言中關(guān)于庫函數(shù) qsort 的模擬實(shí)現(xiàn)過程的文章就介紹到這了,更多相關(guān)C語言 qsort內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)停車場(chǎng)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)停車場(chǎng)管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-01-01C語言強(qiáng)制類型轉(zhuǎn)換規(guī)則實(shí)例詳解
強(qiáng)制類型轉(zhuǎn)換是把變量從一種類型轉(zhuǎn)換為另一種數(shù)據(jù)類型,下面這篇文章主要給大家介紹了關(guān)于C語言強(qiáng)制類型轉(zhuǎn)換的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06詳解C++中的增量運(yùn)算符++和減量運(yùn)算符--的用法
這篇文章主要介紹了C++中的增量運(yùn)算符++和減量運(yùn)算符--的用法,分為前綴情況和后綴情況來講,需要的朋友可以參考下2016-01-01