The use of qsort function and its analog implementation

qsort 函数

函数功能

qsort 是CA sorting function in the language based on the idea of ​​quicksort,Unlike the bubble sort we learned earlier,qsort 可以排序任意类型的数据（整形、浮点型、数组、结构体等等）,同时,qsort Functions are also a classic example of the application of callback functions in function pointers .

函数参数

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

# void* base：The starting address of the data to be sorted,Define the pointer type as void*,让qsortA function can receive the address of any type of data;
# size_t num：要排序的元素个数;
# size_t width：每个元素的大小;
# __cdecl：函数调用约定;
# int (*compare)(const void *elem1, const void *elem2 ))：函数指针,Points to the function used for sorting

函数指针

Suppose I have a file named struct Stu 的结构体,里面有 name、age、height 三个成员变量,现在我们要调用 qsort The function sorts multiple such struct variables,那么这里就会出现一个问题;

struct Stu There are three internal sorting criteria,分别是 name、age 和 height,We, the caller of the function, must know exactly what basis we want to sort by,但是qsort The implementer of the function obviously doesn't know;

所以 qsort The fourth parameter in the function is a function pointer,The function pointer points to a sorting function,The function needs to be set by qsort provided by the caller,Used to specify how two data are compared.

int (*compare)(const void *elem1, const void *elem2 ));
# const void *elem1：The first data for comparison;
# const void *elem2：The second data for comparison;

The return value of the sorting function

-返回值	-对应情况
= 0	Both data are equal
> 0	The first data is greater than the second data
< 0	The first data is smaller than the second data

函数使用

我们以上面提到的 struct Stu Structure for example;

以 name 为依据进行排序：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件
#include <string.h> //strcmp 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_name(const void* e1, const void* e2)  //排序函数
{
    
	//由于e1 e2 是void*类型,不能直接解引用,So we need to cast it first struct Stu* 类型,Then find out which of them name 进行比较
	//由于strcmpThe return value of the function and the sort function are the same,且name是字符串,So here we call directlystrcmp函数
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_name);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

以 age basis for comparison：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_age(const void* e1, const void* e2)  //排序函数
{
    
    //由于e1 e2 是void*类型,不能直接解引用,So we need to cast it first struct Stu* 类型,Then find out which of them age 进行比较
	//According to the return value requirements of the sorting function,We can directly return the difference between the two
	return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_age);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

以 height basis for comparison：

#include <stdio.h>
#include <stdlib.h> //qsort 对应头文件

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_height(const void* e1, const void* e2)  //排序函数
{
    
    //由于e1 e2 是void*类型,不能直接解引用,So we need to cast it first struct Stu* 类型,Then find out which of themheight进行比较
	//According to the return value requirements of the sorting function,We can directly return the difference between the two
	return (((struct Stu*)e1)->height - ((struct Stu*)e2)->height);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	qsort(stu, 3, sizeof(struct Stu), sort_by_height);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

qsort 函数的模拟实现

We learned about bubble sort earlier,我们知道,Bubble sort can only sort integer data;Today we will use the idea of ​​quick sort to transform bubble sort,Let it reach and qsort 函数同样的效果,可以排序任意类型的数据.

冒泡排序

First, let's write a normal bubble sort：

void bubble_sort(int arr[], int n)
{
    
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)
	{
    
		for (j = 0; j < n - i - 1; j++)
		{
    
			if (arr[j] > arr[j + 1])
			{
    
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
    
	int arr[] = {
     1,2,4,5,8,3,6,7,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);  //冒泡排序
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

Now let's modify the bubble sort：

The first is the parameter setting,为了达到和 qsort 函数同样的效果,We have parameters here and qsort 设置为一样;Then comes the concrete realization,We do not need to change the overall framework of bubble sort,The only place to change is the way elements are compared and swapped.

void Swap(char* buf1, char* buf2, size_t width)
{
    
	int i = 0;
	for (i = 0; i < width; i++)  //Swap the contents of each pair of bytes of the two elements
	{
    
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}

void bubble_sort(void* base, size_t num, size_t width, int (*cmp)(const void* e1, const void* e2))
{
    
	int i = 0;
	int j = 0;
	for (i = 0; i < num - 1; i++)
	{
    
		for (j = 0; j < num - i - 1; j++)
		{
    
			//由于base是void*的,So it can't be done directly+-整数的操作
			//At the same time, in order to be able to manipulate any type of data,我们把baseCast to the size of the smallest data type：char*
			//回调函数：Use the return value of the sorting function to determine whether to exchange elements
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
    
				//如果前一个元素>后一个元素,Swap the data of the two elements
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

Now we use the modified bubble sort to sort our struct above,检验代码的正确性：

struct Stu
{
    
	char name[20];
	int age;
	int height;
};

int sort_by_name(const void* e1, const void* e2)  //排序函数：按姓名
{
    
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int sort_by_age(const void* e1, const void* e2)  //排序函数：按年龄
{
    
	return (((struct Stu*)e1)->age - ((struct Stu*)e2)->age);
}

int sort_by_height(const void* e1, const void* e2)  //排序函数：按身高
{
    
	return (((struct Stu*)e1)->height - ((struct Stu*)e2)->height);
}

int main()
{
    
	struct Stu stu[3] = {
     {
    "zhangsan", 23, 185}, {
    "lisi", 20, 180}, {
    "wangwu", 25, 186} };
	int i = 0;
	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_name);
	printf("以姓名排序：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	printf("----------------------\n");

	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_age);
	printf("以年龄排序：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	printf("----------------------\n");

	bubble_sort(stu, 3, sizeof(struct Stu), sort_by_height);
	printf("Sort by weight：\n");
	for (i = 0; i < 3; i++)
	{
    
		printf("姓名：%s\t年龄：%d\t身高：%d\n", stu[i].name, stu[i].age, stu[i].height);
	}
	return 0;
}

We just used bubble sort to simulate the implementation above qsort 函数的功能,并不是说 qsort The inside of the function is also implemented using bubble sort,Doing so clearly outweighs the gains,Because the time complexity of bubble sort is relatively high;But they all achieve the same effect,And they are all designed based on the idea of ​​quick sort.

---