c语言qsort函数的用法与模拟实现

一、qsort函数说明

首先他是一个库函数，在使用时需要包含stdlib.h这个头文件，其次他是一个基于快速排序算法的排序函数，任何类型的数据都可以实现排序，比如字符串排序，结构体排序及整形排序。

二、函数原型

void qsort(void* base,int num,int width,int(*cmp)(void* e1,void* e2))

其中：

base是一个待排序地址的起始位置的指针，使用时传入数组地址即可

num是待排序元素的个数

width是待排序的其中一个元素所占的字节大小

cmp是一个函数指针，指向一个比较函数，而这个函数在我们使用qsort函数时需要自己根据所排序数据的类型进行定义，下面会讲到，这个函数有两个参数

三、用法

1、给一个整形数组进行排序

#include
#include//要引用头文件

int cmp(void* e1, void* e2)
{
	//此处传入的是一个void*类型的指针而待排序的是整形数据，所以强制类型转换为int*，如果是浮点型就转换为对应的指针类型
	return (*((int*)e1) - *((int*)e2));
}

int main()
{
	//定义一个整形数组并初始化
	int a[5] = { 3,1,2,5,4 };

	//调用qsort函数进行排序
	qsort(a, 5, sizeof(a[0]), cmp);//其中a是数组首元素地址也是待排序起始地址，5就是待排序数据个数，sizeof(a[0])就是计算一个待排序元素所占字节大小，cmp就是自己定义的比较函数

	//对排序后进行输出
	int i = 0;
	for (i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}

	return 0;
}

2.对结构体变量进行排序

看一道题 

 

其中对现存确诊人数进行排序

#include
#include

//定义结构体
struct COVID
{
	char name[20];//国家名
	int existdiagnosis;//现存确诊
	int cumulativediagnosis;//累积确诊
	int death;//死亡
	int cure;//治愈
};

//自定义比较现存人数函数
int cmp_by_exist(const void* p1, const void* p2)
{
	return (((struct COVID*)p2)->existdiagnosis - ((struct COVID*)p1)->existdiagnosis);//此处强制类型在转换为结构体指针，因为要降序所以这里改动一下p2放在前面
}

//自定义比较死亡人数函数
int cmp_by_death(const void* e1, const void* e2)
{
	return (((struct COVID*)e2)->death - ((struct COVID*)e1)->death);
}

int main()
{
	//定义结构体数组
	struct COVID arr[3];//这里为了方便输入设置数组长度较小
	struct COVID* p = arr;

	//输入疫情信息
	printf("地区、现存确诊、累计确诊、死亡、治愈人数\n");
	for (int i = 0; i < 3; i++)
	{
		scanf("%s %d %d %d %d", &arr[i].name, &arr[i].existdiagnosis, &arr[i].cumulativediagnosis, &arr[i].death, &arr[i].cure);
	}

	//现存确诊排序qsort
	qsort(arr, 3, sizeof(arr[0]), cmp_by_exist);

	//对排序后数据输出
	printf("地区	现存确诊	累计确诊	死亡	治愈\n");
	for (int i = 0; i < 3; i++)
	{
		printf("%s	%d	%d	%d	%d\n", (p+i)->name, (p+i)->existdiagnosis, (p+i)->cumulativediagnosis, (p+i)->death, (p+i)->cure);
	}

	//找出死亡人数
	qsort(arr, 3, sizeof(arr[0]), cmp_by_death);

	//输出死亡人数最多的地区名称
	printf("\n死亡人数最多的国家是：\n");
	printf("%s\n", arr[0].name);

	return 0;
}

要注意void*类型的指针不能解引用也不能直接加减 

总结：使用该函数时需要自己定义比较函数，比较函数需要根据所排序的数据类型进行定义

四、 使用冒泡排序模拟实现qsort函数

1、先看主函数里，定义一个待排序的数组，任何Mqsort为我们模拟定义的qsort函数，待排序后进行输出看是否成功 

int main()
{
	//定义并初始化要排序的数组
	int arr[10] = { 3,2,4,1,5,7,6,9,8,10 };

	//传入函数
	Mqsort(arr, 10, sizeof(arr[0]), cmp_by_int);

	//输出排序后数组
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

 2、Mqsort函数，用冒泡排序模拟实现，其中在正常的冒泡排序里if语句中是简单的比较大小，而qsort函数是多种类型都可以排序，如果if中是简单的比较大小，那给字符串排序就不行了，使用在if语句里我们使用自定义的比较函数，也就是上面我们所说的随着待排序元素类型的不同去定义的cmp函数，在if语句里正常冒泡排序是利用第三变量去交换两个变量，而同理如果待排序的是字符串呢，那我们第三变量定义为int是不是不可以，所以我们定义函数swap在下面有讲解

//排序函数实现
void Mqsort(void* base, int num, int width, int (*cmp)(void*, void*))
{
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < num - i - 1; j++)
		{
			if ((cmp((char*)base + j * width, (char*)base + (j + 1) * width)) > 0)
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

3、cmp比较函数

	if ((cmp((char*)base + j * width, (char*)base + (j + 1) * width)) > 0)
	{
		swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
	}

	

他有两个参数，都是void*类型的而我们说过这种类型的指针不可以直接加减，所有我们把它强制类型转换为char*类型传入函数,base 是起始地址，把它转换为char*类型之后在访问下一个元素时只需要我们用base+j*width（是待排序数据所占字节）比如一个整形数组比较a[0]与a[1]时base+0*width是a[0]地址而a[1]的地址就是base+（0+1）*width

//自定义比较函数
int cmp_by_int(const void* p, const void* e)
{
	return (*((int*)p) - *((int*)e));
}

 4swap交换两变量

//交换两个变量的函数
void swap(char* e1, char* e2,int w)
{
	for (int i = 0; i < w; i++)
	{
		char temp = *e1;
		*e1 = *e2;
		*e2 = temp;
		e1++;
		e2++;
		//此处定义为char指针一个字节一个字节的去交换，因为不知道要排序的是什么类型的元素
	}
}

用char*类型指针去接收，在交换时，一个字节一个字节交换而不是直接交换比如：1和2要交换

在内存里存储时（此处以大端字节序）

e1:1（16进制）：00 00 00 01

e2:2                  ：00 00 00 02

先访问到第一个字节其中两个数都是00 与00 然后交换

然后e1e2都++访问到第二个字节，也都是00，交换

访问到第四个字节时1是01，而2是02交换两个后

e1:00 00 00 02

e2:00 00 00 01

五、模拟代码

#include

//自定义比较函数
int cmp_by_int(const void* p, const void* e)
{
	return (*((int*)p) - *((int*)e));
}

//交换两个变量的函数
void swap(char* e1, char* e2,int w)
{
	for (int i = 0; i < w; i++)
	{
		char temp = *e1;
		*e1 = *e2;
		*e2 = temp;
		e1++;
		e2++;
		//此处定义为char指针一个字节一个字节的去交换，因为不知道要排序的是什么类型的元素
	}
}

//排序函数实现
void Mqsort(void* base, int num, int width, int (*cmp)(void*, void*))
{
	for (int i = 0; i < num; i++)
	{
		for (int j = 0; j < num - i - 1; j++)
		{
			if ((cmp((char*)base + j * width, (char*)base + (j + 1) * width)) > 0)
			{
				swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
			}
		}
	}
}

int main()
{
	//定义并初始化要排序的数组
	int arr[10] = { 3,2,4,1,5,7,6,9,8,10 };

	//传入函数
	Mqsort(arr, 10, sizeof(arr[0]), cmp_by_int);

	//输出排序后数组
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}