qsort函数的原理及使用

一. qsort功能介绍

qsort函数是给数据进行排序的，排序原理为快速排序，时间复杂nlogn。 排序的数据是任意的,可以是整型 字符型 或 结构体类型 等等。要进行 升序 降序或按 字符大小 排序等都是由自己决定的。

二. qsort的使用

我们打开库函数学习网站(C library - C++ Reference (cplusplus.com))，搜索qsort观察它的参数如下截图：

b9ae632082714581af2d4f87b8fe3b55.png

其中的参数及作用 ： 1.void* base：传入数组地址。 2.size_t num：传入数组长度。 3.size_t size：传入数组中一个元素所占的字节个数。 4.int (*compar)(const void*,const void*)：传入返回类型为int，两参数为const void*的函数的地址。 前三个参数比较容易理解，接下来我们讲一下第4个参数。

要知道qsort是可以用来对任意类型数组排序的，排序就必然要经过比较大小，那么不同类型的数组元素的比较方法是不同的，如 int 类型用>或<比较，字符串类型用strcmp来比较，结构体类型又由里面的成员等因数来决定。

qsort是不知道我们要比较什么类型的，也不知道我们需要什么样的比较规则，那么就要求我们自己来写一个比较两个数据的函数然后传地址给qsort函数，要求自定义函数的返回类型为int，两参数为cost void*类型，其中cost是为了防止用户在写这个函数过程中把数据给改掉，因为不知道用户要排序的数组类型。

所以用void*的好处是任意类型都可以接收。另一个要求是数据 左参数数据>右参数数据 时则返回任意一个大于0的数 左参数数据=右参数数据 时则返回0，左参数数据<右参数数据时则返回任意一个小于0的数。

比如我们写一个整型数组的升序排序的比较函数。

75022b8c668044b6a5a6933eac07334a.png

三. qsort的原理

接下来我们通过用冒泡排序原理来模拟实现一个qsort函数，来深入了解这个函数。在做这个模拟函数的时候要时刻意识到我们并不知道用户要排序的数组类型。

1. void my_qsort(void* arr , size_t sz , size_t width , int (*bj)(const void*, const void*))。
2. my_qsort 函数只需要排序并不需要返回数据所以返回类型为void。
3. void* arr 用来接受任意类型的数组地址。
4. size_t sz 知道数组长度也是必要的，所以我们用一个size_t类型来接收数组长度。
5. size_t width 由于涉及到指针的加法运算，但不知道数据类型（及不知道加多少字节），所以需要一个接收数组中一个元素所占字节个数的参数。
6. int(*bj)(const void*,const void*) 这个函数在上面qsort的使用已经讲过，这里就不再赘述。

接下来给大家带来my_qsort函数的图解：

原码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void Swap(char* p1, char* p2, size_t ssz)//交换元素
{
	for (int i = 0; i < ssz; i++)
	{
		char u = *(p1 + i);
		*(p1 + i) = *(p2 + i);
		*(p2 + i) = u;
	}
}
void my_qsort(void* arr, size_t sz, size_t width, int(*bj)(const void*, const void*))
{
	for (int i = 0; i < sz - 1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (bj((char*)arr + j * width, (char*)arr + (j + 1) * width) > 0)
			{
				Swap((char*)arr + j * width, (char*)arr + (j + 1) * width, width);
			}
		}
	}
}
int sm(const void* p1, const void* p2)//比较大小
{
	return *(int*)p1 - *(int*)p2;
}
void print(int* arr,int sz)//输出函数
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int a[10] = { 0 };
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 10; i++)
	{
		a[i] = rand() % 100 + 1;
		printf("%d ", a[i]);
	}
	printf("\n");
	size_t sz = sizeof(a) / sizeof(a[0]);
	my_qsort(a, sz, sizeof(a[0]), sm);
	print(a, sz);
	return 0;
}