如何使用qort函数

首先需要引入头文件

#include <stdlib.h>
#include <search.h>

 让我们先来看看qsort函数都有哪些参数。

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

 

base：指向目标数组的指针。

num：数组中元素的个数，无符号数

width：数组中元素所占字节数，无符号数

int(_cdecl*compare)(const void *elem1,const void *elem2)：

这个参数表示的是，一个函数指针。函数返回值为lin类型，有两个函数参数，都是void *类型的指针，它们表示的是，数组内两个进行比较的元素。

这里讲解一下，为什么base、elem1、elem2的类型都是void *。这是因为，qsort能都将各种类型的数组进行排序，在使用qsort函数并给它传入数组地址的时候，qsort不能确定接收某一个类型的地址，例如，如果把base的类型改为char *，那么当传入int类型的数组时，代码就会报错误。

void qsort( char *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

所以，使用void *来接收地址的好处就是，void *能够接受任何类型的地址，且不报错。我们只需要在函数内部，将void *类型的地址再转换成我们需要的类型就可以了。

elem1和elem2同理，这两个参数表示的意思是两个进行相比较的元素。当我们不知道用什么类型来接收的时候，就可以用void *来接收。

void *类型的指针有一个缺点，那就是该类型的指针不能够进行运算。

讲解完qsort函数需要有哪些参数了之后，接下来我们的主要工作就是编写比较两个数大小的函数。这里是对应qsort最后一个参数，函数指针。

compare函数的要求是，elem1大于elem2就返回一个正值，elem1小于elem2就返回一个负值，elem1等于elem2就返回一个0；

typedef struct student
{
	char name[20];
	int age;
}test;
//比较整型
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
//比较结构体中的name成员
int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((test*)e1)->name, ((test*)e2)->name);
}
//比较结构体中的age成员
int cmp_by_age(const void* e1, const void* e2)
{
	return ((test*)e1)->age - ((test*)e2)->age;
}

接下来就可以使用qsort函数了。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
//模拟实现qsort函数
//qsort函数的功能是利用冒泡排序法的原理，将各种类型的数据进行排序
typedef struct student
{
	char name[20];
	int age;
}test;
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((test*)e1)->name, ((test*)e2)->name);
}
int cmp_by_age(const void* e1, const void* e2)
{
	return ((test*)e1)->age - ((test*)e2)->age;
}
//整型数组测试函数
void test_int(int* arr_int, int sz)
{
	qsort(arr_int, sz, 4, cmp_int);
	//打印数组
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr_int[i]);
	}
	printf("\n");
}
//结构体数组测试函数
void test_struct(test* stu1, int sz)
{
	qsort(stu1, sz, sizeof(stu1[0]), cmp_by_age);//结构体按成员age排序
	for (int i = 0; i < sz; i++)
	{
		printf("%s ", stu1[i].name);
		printf("%d\n", stu1[i].age);
	}
}
int main()
{
	test s1[4] = { {"张三",18},{"李四",20},{"王五",30},{"盖伦",28} };
	int arr[] = { 5,6,1,2,4,7,8,3,9 };
	unsigned int len1 = sizeof(arr) / sizeof(arr[0]);
	unsigned int len2 = sizeof(s1) / sizeof(s1[0]);
	//测试使用qsort函数
	test_int(arr, len1);
	test_struct(s1, len2);
	return 0;
}

输出结果：

可以看出，整型数组已经按照从小到大的顺序排列好，结构体数组也已经按照成员age的大小排序好。按照成员name排序，只需要在给qsort函数传入参数的时候，将cmp_by_age换成cmp_by_name就可以了。

 我展示一下结构体按照成员name排序的输出结果。

 模拟实现qsort函数

主要是利用冒泡排序的方法进行排序。

这里主要讲解，函数内部两个数据是如何进行计较以及交换的。

void My_qsort(void* base, size_t num, size_t width, int(*cmp)(const void* elem1, const void* elem2))
{                                              //回调函数
	size_t i = 0;
	for (i = 0; i < num - 1; i++)
	{
		size_t j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			//if (cmp(elem1,elem2)>0)//如果返回值是0，表示元素1大于元素2，那么就进行交换
			//{
				//交换
			//}
		}
	}
}

问题在于，我们只得到了一个void *类型的数组地址，该如何确定出，这个数组中的元素呢？

毫无疑问，肯定需要先将void *类型的地址转换成其他的类型才可以进行运算。我们调用cmp函数的时候，我们只需要传入两个相邻数据地址即可，因为cmp函数内部会帮我们转换数据类型并进行比较。那么该如何找到两个相邻数据的地址呢？

可以将void *base转换成char *base，然后elem1和elem2的地址就可以表示成base和base+width

所以在上图的基础上，elem1的地址可以表示为 base + j * width，elem2的地址表示为base + (j + 1) * width。这表示，当第i趟j次比较的时候，元素elem1和elem2的地址。

接下来就是将两个数据进行交换

采用字节逐一交换的方法

void Swap(char* buf, int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *buf;
		*buf = *(buf + width);
		*(buf + width) = tmp;
		buf++;
	}
}

最后，模拟实现qsort函数就完成了，以下是代码展示。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
//模拟实现qsort函数
//qsort函数的功能是利用冒泡排序法的原理，将各种类型的数据进行排序
//void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ));
typedef struct student
{
	char name[20];
	int age;
}test;
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int cmp_by_name(const void* e1, const void* e2)
{
	return strcmp(((test*)e1)->name, ((test*)e2)->name);
}
int cmp_by_age(const void* e1, const void* e2)
{
	return ((test*)e1)->age - ((test*)e2)->age;
}
void Swap(char* buf, int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *buf;
		*buf = *(buf + width);
		*(buf + width) = tmp;
		buf++;
	}
}
//升序
void My_qsort(void* base, size_t num, size_t width, int(*cmp)(const void* elem1, const void* elem2))
{                                              //回调函数
	size_t i = 0;
	for (i = 0; i < num - 1; i++)
	{
		size_t j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width)>0)//>0
			{
				Swap((char*)base + j * width, width);
			}
		}
	}
}
//整型数组测试函数
void test_int(int* arr_int, int sz)
{
	My_qsort(arr_int, sz, 4, cmp_int);
	//打印数组
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr_int[i]);
	}
	printf("\n");
}
void test_struct(test* stu1, int sz)
{
	My_qsort(stu1, sz, sizeof(stu1[0]), cmp_by_name);
	for (int i = 0; i < sz; i++)
	{
		printf("%s ", stu1[i].name);
		printf("%d\n", stu1[i].age);
	}
}
int main()
{
	test s1[4] = { {"张三",18},{"李四",20},{"王五",30},{"盖伦",28} };
	int arr[] = { 5,6,1,2,4,7,8,3,9 };
	unsigned int len1 = sizeof(arr) / sizeof(arr[0]);
	unsigned int len2 = sizeof(s1) / sizeof(s1[0]);
	//测试使用qsort函数
	test_int(arr, len1);
	test_struct(s1, len2);
	return 0;
}