C语言中关于库函数 Qsort 的模拟实现过程

前言

我们在上一篇博客讲解了库函数qsort的使用,今天我为大家带来qsort的模拟实现。上一篇博客这个库函数的阅读链接:C语言中关于库函数 Qsort 快排的用法

其实有人会问,我明明已经掌握了库函数qsort的使用方法,为何还要去写模拟实现,其实啊,学好一个东西,不仅仅只是会用就可以,如果我们能更深层次的去探索这个函数是怎么实现的,我相信,这其中的乐趣,不一般。。。

仅以此篇文章作为我学习的见证,希望能够各位带来一定的帮助,谢谢。文章若有不妥之处,欢迎指点。这是一个共同进步的平台!!!

一、qsort函数

我们先看看qsort函数的使用:

#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函数的四个参数我们就不过多讲了。大家翻一翻上一篇博客。

二、qsort函数实现思路
1. 底层原理

其实啊,qsort函数,底层原理是 快速排序,只不过我们在使用的时候,被封装成了函数而已。我们写的是从冒泡排序的角度写。

2. 函数传参
qsort(arr, sz, sizeof(arr[0]), cmp_int);
1). 第一个参数

传入的是一个数组,可能大多数人的第一反应就是对应函数的形参用数组指针来接收,我当初自己在写的时候,也是这样想的,当我们越往后面写,发现这个形参用数组指针来接收,并不好用,至于为什么,往下看。

我们在上一篇博客提到过 void* 这个概念,它能接收来自所有类型的值,我们这第一个参数的形参就写成 void* base

2). 第二个参数

传入的是元素个数,我们再提到一个概念:size_t 返回类型,它是一个无符号整形(unsigned int),我在《C primer plus》书找到了相关的解释,图放在下面:

D6975920-FCF1-50EF-6805-FBC7ECC60368.png

因为我们传第二个参数时,传的其实就是sizeof的返回值,所有函数形参部分就写 size_t sz

3). 第三个参数

这第三个参数啊,跟第二个参数是一样的,计算得到的也是sizeof的返回值,也直接写size_t width。(代表一个元素的大小)

4). 第四个参数

这第四个参数是一个函数啊,我们在传参的时候,传的其实是这个函数的地址啊,在my_sort(就是等会我们需要实现的qsort函数),在my_sort函数里面,我们通过传过来的函数地址(cmp_int)去调用这个(cmp_int)函数,我们就叫回调函数。这里有点绕,仔细品。

既然传过来的是一个函数的地址,对应的,我们就用函数指针去接收,具体的代码看下面:

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

有的小伙伴就会问函数指针是是什么?

就是用来接收函数的地址,用的指针,具体的原理,大家可以去CSDN查,这里,我们就不多讲了。

局部代码:

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函数里面实则还是冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			//进行判断和交换
			
			
		}
	}
}

这就是qsort函数大致的框架,还有一点点小细节问题,处理了就完成了,加油哦。

三、局部函数实现

现在放在我们面前的问题,怎么进行数值的判断和交换。

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

我们以这个数组为例,我们想想,如果我们要排一个升序的数组,只需要我们传递给(cmp_int)函数的两个参数相减为正数,上一篇博客提到了口诀“左减右为升序,反之则降”,即就是e1 - e2 大于0 ,也就是e1>e2了。 注:函数参数(const void* e1,const void* e2)

知道了其中原理,就好实现了呗,if语句判断,如果(cmp_int)函数的放回值大于0,我们就交换一下两个数。

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函数里面实则还是冒泡排序
	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)
			{
				//此处函数传参的时,并非只需要传递两个需要交换的数据,还有数据的大小,即就是字节数
				//例如是整体数据交换,而Swap函数,其实函数里面需要循环4次才行,因为是4个字节的数据嘛
				Exch((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

随着j的增加,我们比较的数据也一个个的往后移,特别注意(char*) base + j * width,我们在使用base时,必须先要进行强制类型转换,这样再进行加减操作才可以。因为 base的类型是 void * 类型,没有具体的大小。强制类型转换后,再加上j*width个字节,这样就能找到数组中一个个的元素。

接下来就是函数Exch的实现,这个函数就是交换两个数的位置用的,(exchange)。上面的if语句如果成立,我们就调用函数Exch,去交换两个数的位置,传参的话,跟if语句里面的参数一样的,毋庸置疑。只是我们在传参的时候,还需要传第三个参数width,因为我们调用函数Exch后,函数里面一次交换,只能交换1个字节的内容。有小伙伴就会问,我一次直接交换4个字节的内容,这不是简单的多了嘛。。。。

对于整形数组,一次直接交换4个字节的内容,当然简单了,但是我们需要交换其他数据类型的时候呢,难道还要重新写一遍my_sort吗??是吧,所以,1个字节慢慢交换,循环width次就行,这样写出来的函数,才是通用的。

Exch函数的实现

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++; //逗号表达式,从左到右,依次执行
	}
}

这里面就简单多了,就是创建一个临时变量 ,交换数据后,对应的地址加1即可,特别注意一下函数形参部分哦,为什么要写 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++; //逗号表达式,从左到右,依次执行
	}
}

void my_sort(void* base, size_t sz, size_t width, int (*cmp)(void*, void*))
{
	//函数里面实则还是冒泡排序
	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)
			{
				//此处函数传参的时,并非只需要传递两个需要交换的数据,还有数据的大小,即就是字节数
				//例如是整体数据交换,而Swap函数,其实函数里面需要循环4次才行,因为是4个字节的数据嘛
				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;
}
五、总结

简单的给大家说了一下整体代码的思路,还有细节问题,没能给大家表达清楚,我感到非常遗憾。

特别注意一下冒泡排序里面的逻辑,又特别是里面的if语句,这是整个代码的关键,其他的就没多大的问题,捋清楚了,这些,应该就能懂了,还有就是指针哦,虽然有点难,但是始终相信功夫不负有心人!

如果还有什么不理解的,我们在评论区聊,共同进步。加油!!

下次见!!!

收藏 (0)
评论列表
正在载入评论列表...
我是有底线的
为您推荐
    暂时没有数据