前言

我們?cè)谏弦黄┛椭v解了庫(kù)函數(shù)qsort的使用，今天我為大家?guī)?lái)qsort的模擬實(shí)現(xiàn)。上一篇博客這個(gè)庫(kù)函數(shù)的閱讀鏈接：C語(yǔ)言中關(guān)于庫(kù)函數(shù) qsort 快排的用法

其實(shí)有人會(huì)問(wèn)，我明明已經(jīng)掌握了庫(kù)函數(shù)qsort的使用方法，為何還要去寫(xiě)模擬實(shí)現(xiàn)，其實(shí)啊，學(xué)好一個(gè)東西，不僅僅只是會(huì)用就可以，如果我們能更深層次的去探索這個(gè)函數(shù)是怎么實(shí)現(xiàn)的，我相信，這其中的樂(lè)趣，不一般。。。

僅以此篇文章作為我學(xué)習(xí)的見(jiàn)證，希望能夠各位帶來(lái)一定的幫助，謝謝。文章若有不妥之處，歡迎指點(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ù)我們就不過(guò)多講了。大家翻一翻上一篇博客。

二、qsort函數(shù)實(shí)現(xiàn)思路

1. 底層原理

其實(shí)啊，qsort函數(shù)，底層原理是 快速排序,只不過(guò)我們?cè)谑褂玫臅r(shí)候，被封裝成了函數(shù)而已。我們寫(xiě)的是從冒泡排序的角度寫(xiě)。

2. 函數(shù)傳參

qsort(arr, sz, sizeof(arr[0]), cmp_int);

1). 第一個(gè)參數(shù)

傳入的是一個(gè)數(shù)組，可能大多數(shù)人的第一反應(yīng)就是對(duì)應(yīng)函數(shù)的形參用數(shù)組指針來(lái)接收，我當(dāng)初自己在寫(xiě)的時(shí)候，也是這樣想的，當(dāng)我們?cè)酵竺鎸?xiě)，發(fā)現(xiàn)這個(gè)形參用數(shù)組指針來(lái)接收，并不好用，至于為什么，往下看。

我們?cè)谏弦黄┛吞岬竭^(guò) void* 這個(gè)概念，它能接收來(lái)自所有類(lèi)型的值，我們這第一個(gè)參數(shù)的形參就寫(xiě)成 void* base。

2). 第二個(gè)參數(shù)

傳入的是元素個(gè)數(shù)，我們?cè)偬岬揭粋€(gè)概念：size_t 返回類(lèi)型，它是一個(gè)無(wú)符號(hào)整形（unsigned int），我在《C primer plus》書(shū)找到了相關(guān)的解釋?zhuān)瑘D放在下面：

因?yàn)槲覀儌鞯诙€(gè)參數(shù)時(shí)，傳的其實(shí)就是sizeof的返回值，所有函數(shù)形參部分就寫(xiě) size_t sz。

3). 第三個(gè)參數(shù)

這第三個(gè)參數(shù)啊，跟第二個(gè)參數(shù)是一樣的，計(jì)算得到的也是sizeof的返回值，也直接寫(xiě)size_t width。（代表一個(gè)元素的大小）

4). 第四個(gè)參數(shù)

這第四個(gè)參數(shù)是一個(gè)函數(shù)啊，我們?cè)趥鲄⒌臅r(shí)候，傳的其實(shí)是這個(gè)函數(shù)的地址啊，在my_sort(就是等會(huì)我們需要實(shí)現(xiàn)的qsort函數(shù))，在my_sort函數(shù)里面，我們通過(guò)傳過(guò)來(lái)的函數(shù)地址（cmp_int）去調(diào)用這個(gè)（cmp_int）函數(shù),我們就叫回調(diào)函數(shù)。這里有點(diǎn)繞，仔細(xì)品。

既然傳過(guò)來(lái)的是一個(gè)函數(shù)的地址，對(duì)應(yīng)的，我們就用函數(shù)指針去接收，具體的代碼看下面：

void my_sort(void* base, 
			size_t sz, 
			size_t width, 
			int (*cmp)(void*, void*));

有的小伙伴就會(huì)問(wèn)函數(shù)指針是是什么？
就是用來(lái)接收函數(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é)問(wèn)題，處理了就完成了，加油哦。

三、局部函數(shù)實(shí)現(xiàn)

現(xiàn)在放在我們面前的問(wè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語(yǔ)句判斷，如果（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)制類(lèi)型轉(zhuǎn)換，這樣再進(jìn)行加減操作才可以。因?yàn)?base的類(lèi)型是 void * 類(lèi)型，沒(méi)有具體的大小。強(qiáng)制類(lèi)型轉(zhuǎn)換后，再加上j*width個(gè)字節(jié)，這樣就能找到數(shù)組中一個(gè)個(gè)的元素。

接下來(lái)就是函數(shù)Exch的實(shí)現(xiàn)，這個(gè)函數(shù)就是交換兩個(gè)數(shù)的位置用的，（exchange）。上面的if語(yǔ)句如果成立，我們就調(diào)用函數(shù)Exch，去交換兩個(gè)數(shù)的位置，傳參的話，跟if語(yǔ)句里面的參數(shù)一樣的，毋庸置疑。只是我們?cè)趥鲄⒌臅r(shí)候，還需要傳第三個(gè)參數(shù)width，因?yàn)槲覀冋{(diào)用函數(shù)Exch后，函數(shù)里面一次交換，只能交換1個(gè)字節(jié)的內(nèi)容。有小伙伴就會(huì)問(wèn)，我一次直接交換4個(gè)字節(jié)的內(nèi)容，這不是簡(jiǎn)單的多了嘛。。。。
對(duì)于整形數(shù)組，一次直接交換4個(gè)字節(jié)的內(nèi)容，當(dāng)然簡(jiǎn)單了，但是我們需要交換其他數(shù)據(jù)類(lèi)型的時(shí)候呢，難道還要重新寫(xiě)一遍my_sort嗎？？是吧，所以，1個(gè)字節(jié)慢慢交換，循環(huán)width次就行，這樣寫(xiě)出來(lái)的函數(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ù)形參部分哦，為什么要寫(xiě) 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)單的給大家說(shuō)了一下整體代碼的思路，還有細(xì)節(jié)問(wèn)題，沒(méi)能給大家表達(dá)清楚，我感到非常遺憾。
特別注意一下冒泡排序里面的邏輯，又特別是里面的if語(yǔ)句，這是整個(gè)代碼的關(guān)鍵，其他的就沒(méi)多大的問(wèn)題，捋清楚了，這些，應(yīng)該就能懂了，還有就是指針哦，雖然有點(diǎn)難，但是始終相信功夫不負(fù)有心人！
如果還有什么不理解的，我們?cè)谠u(píng)論區(qū)聊，共同進(jìn)步。加油??！
下次見(jiàn)?。?！

到此這篇關(guān)于C語(yǔ)言中關(guān)于庫(kù)函數(shù) qsort 的模擬實(shí)現(xiàn)過(guò)程的文章就介紹到這了,更多相關(guān)C語(yǔ)言 qsort內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論