深入解析 qsort 排序（上），它为什么是万能排序？

逃离我推掉我的手 2023-10-15 22:12 7阅读 0赞

>  **前言：**对于库函数有适当了解的朋友们，对于 qsort 函数想必是有认知的，因为他可以对任意数据类型进行排序的功能属实是有点厉害的，本次分享，笔者就给大家带来 qsort 函数的全面的解读

**本次知识的分享笔者分为上下俩卷文章进行讲解，在本篇文章中，给大家带来 qsort 函数的基础认知，以及他如何进行功能实现的背后原理讲解**

> **下卷：**[深入解析 qsort 函数（下），用冒泡排序模拟实现 qsort 函数][qsort _ qsort]

--------------------

**目录**

一.什么是 qsort 函数

二. qsort 的使用

1.对于整形数组的排序

2.对于浮点型数组的排序

3.对于结构体数组的排序

通过姓名首字母排序

通过年龄进行排序

--------------------

## 一.什么是 qsort 函数 ##

我们打开 **cplusplus** 网站查看详细定义

> [qsort - C++ Reference (cplusplus.com)][qsort - C_ Reference _cplusplus.com]

![192e754dfa3b4194adb976fac65beaa3.png][]

在官方的定义中是这样说的：

>  *  对所指向的数组元素进行排序，每个元素长度为字节，使用函数确定顺序
>  *  此函数使用的排序算法通过调用指定的函数，将指向元素的指针作为参数来比较元素对
>  *  该函数不返回任何值，但通过重新排序所定义的元素来修改所指向数组的内容
>  *  等效元素的顺序未定义

翻译成我们自己的语言就是，**这个函数是用来对数组元素排序的**，**我们自己用函数来确定排序的规则** ，并且对于数组元素的类型是没有作任何要求的，这也就意味着，**我们可以对任意类型的元素进行任意规则的排序**

> 还是看上图，这个函数有 4 个参数，并且不进行返回值，我们接下来分别解析一下具体是怎么样的一个意思：
> 
>     void qsort (void* base, 
>     			size_t num,
>     			size_t size,
>     			int (*compar)(const void*, const void*));

![753b1c62d4614374a1e379169809f245.png][]

对于这样的文本，我们还是要转化为自己好理解的方式：

> 1.  **void\* base：**待排序数组的第一个元素的地址
> 2.  **size\_t num：**待排序数组的元素个数
> 3.  **size\_t size：**待排序数组中一个元素的大小
> 4.  **int (\*compar)(const void\*, const void\*)：**函数指针-cmp指向了一个函数，这个函数是用来比较两个元素的，e1和e2中存放的是需要比较的两个元素的地址

> 另外，对于第 4 点，也就是具体比较方法的函数，它的返回值是需要注意的，只返回三类值，大于零，等于零，小于零，具体含义在后文实例中进行讲解，这里就不再多做赘述
> 
> ![d677ba805586446abffab5bb58fdd79f.png][]

## 二. qsort 的使用 ##

### 1.对于整形数组的排序 ###

我们定义一个整型数组

int arr1[10] = { 0,1,2,3,4,5,6,7,8,9 };

然后定义一个函数打印数组方便我们观察

void print1(int* arr)
    {
    	for (int i = 0; i < 10; i++)
    	{
    		printf("%d ", *(arr + i));
    	}
    	printf("\n");
    }

**然后我们调用 qsort 进行排序，在这里我们详细的看看四个参数：**

*  第一个参数 arr1，指向数组arr1，我们就得到了需要排序的数组的第一个元素的地址
 *  第二个参数 10，代表的是这个数组的大小是 10
 *  第三个参数 4，代表的是数组元素的字节大小，arr1 是个整形数组，整形 int 是 4 个字节，所以这里的参数是4
 *  第四个参数 comp\_int，这是个函数，更是它这个函数本身的地址，我们将这里的函数地址作为参数，就可以调用我们的判断规则的函数

qsort(arr1, 10, 4, comp_int);

int comp_int(const void* a,const void* b)
    {
    	return *(int*)b - *(int*)a;
    }

判断函数这里更是我们需要注意的地方，我们进入到判断函数中，这个判断函数又有俩个参数，都是 **void\*** 的类型，这样设定的目的是为了拿到一个地址，为了**泛型编程**的思想，**我们这里只管拿到地址，不需要思考怎么处理这俩个地址，所以使用 void\* 这样就能满足更多的需求**，后期我们想要更改判断条件的话，也只需要更改这个函数内部的数据，不影响我们整体传参，这是一种非常高级的编程思想，我们可以进行适当的学习，同时在公司内部编程的时候，往往是很多人进行编程一个程序，这样设置更是为了方便这种**团队编程**的思想和功能

进入函数体，我们首先先确定我们的具体需求，我们要的是俩个整数进行比较，但是这里我们拿到的地址是 **void\*** 类型的，所以我们需要进行**强制转化**，把俩个参数转化为整形，这样才能满足我们的需求，拿到整形地址后对其解引用就可以访问里面的数据然后进行判断了，**这里我们设置的是如果 b>a 就返回正值，也就是后面的数字大于前面的数字的情况下，我们才进行交换**

> **输出结果实例如下，我们可以看见，对于原本升序的数组，经过我们的排序后，就变成了降序**
> 
>     int arr1[10] = { 0,1,2,3,4,5,6,7,8,9 };
>     	print1(arr1);
>     	qsort(arr1, 10, 4, comp_int);
>     	print1(arr1);
> 
> ![cc3fecc973c3404791ec040b80a7275b.png][]

### 2.对于浮点型数组的排序 ###

和刚才整形数组的排序类似，我们定义一个浮点型数组，然后在排序前和排序后分别进行打印一次，我们这里需要重点观察的是他的判断函数，也就是他的第四个参数

float arr2[5] = { 1.2,3.4,5.6,7.8,9.9 };
    	print2(arr2);
    	qsort(arr2, 5, sizeof(float), comp_float);
    	print2(arr2);

我们观察判断函数，我们发现对于 void\* 类型的转化为浮点型指针，然后进行解引用访问，我们试着运行一下看看可不可以这样写

int comp_float(const void* a, const void* b)
    {
    	return *(float*)b - *(float*)a;
    }

> 经过实验，我们发现 void\* 类型强制转化为浮点型也是可以正常运行的，这里也就验证了我们刚才说过的泛型编程的思想
> 
> ![75fb3fdcd7fb404ca81026c0c9c374a5.png][]

### 3.对于结构体数组的排序 ###

刚才简单的数据类型我们都实验过了，我们好像可以发现这样设置判断函数非常的方便，参数内不管接受什么数据类型，统一写 void\* 类型就可以了，那我们现在不妨试一些复杂的数据类型 —— **结构体数组**

在一切实验之前，我们先得写一个结构体类型，还有其对于的结构体数组，我们写个学生的结构体，内容由学生姓名和年龄组成

struct stu
    {
    	char name[20];
    	int age;
    };

然后对于结构体数组，我们分别如下定义，张三19岁，李四20岁，王五21岁

struct stu arr3[] ={
       {"zhangsan",19},{"lisi",20},{"wangswu",21}};

做好一切准备工作后，我们进行 qsort 排序的设置，我们可以分为俩种方式排序，一种是用姓名首字母进行排序，一种是由年龄大小进行排序

#### 通过姓名首字母排序 ####

我们如下设置，我们来看看 qsort 的四个参数：

*  第一个参数 arr3，指向的是结构体数组的第一个元素的地址
 *  第二个参数 3，代表的是这个结构体数组一共有 3 个元素
 *  第三个参数 sizeof(arr3\[0\])，代表的是结构体数组的每一个元素的大小，这一个元素包含了学生的姓名和年龄
 *  第四个参数 comp\_name，代表的是排序的规则函数

qsort(arr3, 3, sizeof(arr3[0]), comp_name);

int comp_name(const void* a, const void* b)
    {
    	return strcmp(((struct stu*)a)->name, ((struct stu*)b)->name);
    }

我们还是重点看一下排序规则的函数，参数方面还是和我们上面讲的一样，俩个 void\* 方便我们后期修改，进入函数体，我们将俩个参数强制转化为结构体类型，然后分别指向结构体内部的姓名变量；然后我们调用了 **strcmp** 函数，这个函数的功能是**比较俩个字符串的首元素的 ACSSII 大小，然后进行返回值**，返回值和外边的比较方法的返回值的格式和大小一模一样，如下图

![e6b6d7e8c9544fc9b3464732e3fe636f.png][]

#### 通过年龄进行排序 ####

相较于上述的姓名排序，这里的年龄排序就简单的多了

qsort(arr3, 3, sizeof(arr3[0]), comp_age);

int comp_age(const void* a, const void* b)
    {
    	return ((struct stu*)b)->age - ((struct stu*)a)->age;
    }

我们这里对年龄整体的处理和上述的整形数组的处理是一样的，唯一不同的就是我们拿到数据的方式，我们先将其强制转换为结构体类型，然后通过结构体类型指向的年龄进行比较

--------------------

**通过了上述的实例讲述，我们明白了，对于任何的数据类型，我们在拿这个参数的时候，都是用 void\* 类型进行取址，然后对于具体比较操作的时候，我们再将其进行具体的操作，强制转化为我们需要的数据类型，然后进行排序，这样就实现了其 “万能排序” 的功能**

> **下一篇文章我们就探讨如何对 qsort 函数的模拟实现**
> 
> **链接奉上：**[深入解析 qsort 函数（下），用冒泡排序模拟实现 qsort 函数][qsort _ qsort]

[qsort _ qsort]: https://blog.csdn.net/m0_69519887/article/details/132896910?spm=1001.2014.3001.5501
[qsort - C_ Reference _cplusplus.com]: https://legacy.cplusplus.com/reference/cstdlib/qsort/?kw=qsort
[192e754dfa3b4194adb976fac65beaa3.png]: https://img-blog.csdnimg.cn/192e754dfa3b4194adb976fac65beaa3.png
[753b1c62d4614374a1e379169809f245.png]: https://img-blog.csdnimg.cn/753b1c62d4614374a1e379169809f245.png
[d677ba805586446abffab5bb58fdd79f.png]: https://img-blog.csdnimg.cn/d677ba805586446abffab5bb58fdd79f.png
[cc3fecc973c3404791ec040b80a7275b.png]: https://img-blog.csdnimg.cn/cc3fecc973c3404791ec040b80a7275b.png
[75fb3fdcd7fb404ca81026c0c9c374a5.png]: https://img-blog.csdnimg.cn/75fb3fdcd7fb404ca81026c0c9c374a5.png
[e6b6d7e8c9544fc9b3464732e3fe636f.png]: https://img-blog.csdnimg.cn/e6b6d7e8c9544fc9b3464732e3fe636f.png