前言

我們在上一篇博客講解了庫函數(shù)qsort的使用，今天我為大家?guī)韖sort的模擬實現(xiàn)。上一篇博客這個庫函數(shù)的閱讀鏈接：C語言中關(guān)于庫函數(shù) qsort 快排的用法

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

僅以此篇文章作為我學(xué)習(xí)的見證，希望能夠各位帶來一定的幫助，謝謝。文章若有不妥之處，歡迎指點。這是一個共同進步的平臺?。。?/p>

一、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ù)的四個參數(shù)我們就不過多講了。大家翻一翻上一篇博客。

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

1. 底層原理

其實啊，qsort函數(shù)，底層原理是 快速排序,只不過我們在使用的時候，被封裝成了函數(shù)而已。我們寫的是從冒泡排序的角度寫。

2. 函數(shù)傳參

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

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

傳入的是一個數(shù)組，可能大多數(shù)人的第一反應(yīng)就是對應(yīng)函數(shù)的形參用數(shù)組指針來接收，我當初自己在寫的時候，也是這樣想的，當我們越往后面寫，發(fā)現(xiàn)這個形參用數(shù)組指針來接收，并不好用，至于為什么，往下看。

我們在上一篇博客提到過 void* 這個概念，它能接收來自所有類型的值，我們這第一個參數(shù)的形參就寫成 void* base。

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

傳入的是元素個數(shù)，我們再提到一個概念：size_t 返回類型，它是一個無符號整形（unsigned int），我在《C primer plus》書找到了相關(guān)的解釋，圖放在下面：

因為我們傳第二個參數(shù)時，傳的其實就是sizeof的返回值，所有函數(shù)形參部分就寫 size_t sz。

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

這第三個參數(shù)啊，跟第二個參數(shù)是一樣的，計算得到的也是sizeof的返回值，也直接寫size_t width。（代表一個元素的大?。?/p>

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

這第四個參數(shù)是一個函數(shù)啊，我們在傳參的時候，傳的其實是這個函數(shù)的地址啊，在my_sort(就是等會我們需要實現(xiàn)的qsort函數(shù))，在my_sort函數(shù)里面，我們通過傳過來的函數(shù)地址（cmp_int）去調(diào)用這個（cmp_int）函數(shù),我們就叫回調(diào)函數(shù)。這里有點繞，仔細品。

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

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

有的小伙伴就會問函數(shù)指針是是什么？
就是用來接收函數(shù)的地址，用的指針，具體的原理，大家可以去CSDN查，這里，我們就不多講了。

局部代碼：

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函數(shù)里面實則還是冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			//進行判斷和交換
			
			
		}
	}
}

這就是qsort函數(shù)大致的框架，還有一點點小細節(jié)問題，處理了就完成了，加油哦。

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

現(xiàn)在放在我們面前的問題，怎么進行數(shù)值的判斷和交換。

int arr[10]={2,1,4,5,6,3};

我們以這個數(shù)組為例，我們想想，如果我們要排一個升序的數(shù)組，只需要我們傳遞給（cmp_int）函數(shù)的兩個參數(shù)相減為正數(shù)，上一篇博客提到了口訣“左減右為升序，反之則降”，即就是e1 - e2 大于0 ,也就是e1>e2了。 注：函數(shù)參數(shù)（const void* e1，const void* e2）

知道了其中原理，就好實現(xiàn)了唄，if語句判斷，如果（cmp_int）函數(shù)的放回值大于0，我們就交換一下兩個數(shù)。

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函數(shù)里面實則還是冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			//進行判斷和交換
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//此處函數(shù)傳參的時，并非只需要傳遞兩個需要交換的數(shù)據(jù)，還有數(shù)據(jù)的大小，即就是字節(jié)數(shù)
				//例如是整體數(shù)據(jù)交換，而Swap函數(shù)，其實函數(shù)里面需要循環(huán)4次才行，因為是4個字節(jié)的數(shù)據(jù)嘛
				Exch((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

隨著j的增加，我們比較的數(shù)據(jù)也一個個的往后移，特別注意(char*) base + j * width,我們在使用base時，必須先要進行強制類型轉(zhuǎn)換，這樣再進行加減操作才可以。因為 base的類型是 void * 類型，沒有具體的大小。強制類型轉(zhuǎn)換后，再加上j*width個字節(jié)，這樣就能找到數(shù)組中一個個的元素。

接下來就是函數(shù)Exch的實現(xiàn)，這個函數(shù)就是交換兩個數(shù)的位置用的，（exchange）。上面的if語句如果成立，我們就調(diào)用函數(shù)Exch，去交換兩個數(shù)的位置，傳參的話，跟if語句里面的參數(shù)一樣的，毋庸置疑。只是我們在傳參的時候，還需要傳第三個參數(shù)width，因為我們調(diào)用函數(shù)Exch后，函數(shù)里面一次交換，只能交換1個字節(jié)的內(nèi)容。有小伙伴就會問，我一次直接交換4個字節(jié)的內(nèi)容，這不是簡單的多了嘛。。。。
對于整形數(shù)組，一次直接交換4個字節(jié)的內(nèi)容，當然簡單了，但是我們需要交換其他數(shù)據(jù)類型的時候呢，難道還要重新寫一遍my_sort嗎？？是吧，所以，1個字節(jié)慢慢交換，循環(huán)width次就行，這樣寫出來的函數(shù)，才是通用的。
Exch函數(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++; //逗號表達式，從左到右，依次執(zhí)行
	}
}

這里面就簡單多了，就是創(chuàng)建一個臨時變量 ，交換數(shù)據(jù)后，對應(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++; //逗號表達式，從左到右，依次執(zhí)行
	}
}

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函數(shù)里面實則還是冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			//進行判斷和交換
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//此處函數(shù)傳參的時，并非只需要傳遞兩個需要交換的數(shù)據(jù)，還有數(shù)據(jù)的大小，即就是字節(jié)數(shù)
				//例如是整體數(shù)據(jù)交換，而Swap函數(shù)，其實函數(shù)里面需要循環(huán)4次才行，因為是4個字節(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é)問題，沒能給大家表達清楚，我感到非常遺憾。
特別注意一下冒泡排序里面的邏輯，又特別是里面的if語句，這是整個代碼的關(guān)鍵，其他的就沒多大的問題，捋清楚了，這些，應(yīng)該就能懂了，還有就是指針哦，雖然有點難，但是始終相信功夫不負有心人！
如果還有什么不理解的，我們在評論區(qū)聊，共同進步。加油?。?br /> 下次見?。?！

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