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

编辑: admin 分类: c#语言发布时间: 2021-12-12 来源:互联网

前言

我们在上一篇博客讲解了库函数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》书找到了相关的解释，图放在下面：

在这里插入图片描述

因为我们传第二个参数时，传的其实就是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语句，这是整个代码的关键，其他的就没多大的问题，捋清楚了，这些，应该就能懂了，还有就是指针哦，虽然有点难，但是始终相信功夫不负有心人！
如果还有什么不理解的，我们在评论区聊，共同进步。加油！！
下次见！！！

到此这篇关于C语言中关于库函数 qsort 的模拟实现过程的文章就介绍到这了,更多相关C语言 qsort内容请搜索海外IDC网以前的文章或继续浏览下面的相关文章希望大家以后多多支持海外IDC网！

【文章转自：http://www.1234xp.com/xjp.html 复制请保留原URL】

海外服务器