C语言标准库函数qsort( )——数据排序

你的名字 2023-10-03 19:54 137阅读 0赞

![30adcf5df8b44dc8bc660f667cada2c4.jpeg][]

大家好！我是保护小周ღ，本期为大家带来的是深度解剖C语言标准库函数 qsort()，**qsort()函数他可以对任意类型的数据排序，**博主会详细解释函数使用方法，以及使用快速排序的左右指针法模拟实现函数功能**，**这样的排序确定不来学习一下吗？？？

![f89deef4fd5b408f8b4b1c0a50c0a9e9.png][]

![8b354a7916f240d0bc7839822301ba90.gif\#pic\_center][8b354a7916f240d0bc7839822301ba90.gif_pic_center]

**目录**

一、qsort()函数简介

二、qsort() 函数的参数

三、qsort() 函数的使用

3.1 对整型数据排序

3.2 对结构体类型数据排序

四、快速排模拟实现qsort()函数

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

## 一、qsort()函数简介 ##

**qsort()** 函数是**C语言标准库**提供的**排序函数**，q==Quick，函数内部是以快速排序的思想实现的，那qsort() 函数的意义是什么呢？内部居然还使用别的排序的思想。因为常规排序是写死的，假如原先是对整型数据的排序，现在要对结构体类型的数据排序，则需要修改函数参数，函数内部数据也要相应的修改。而**qsort()函数他可以对任意类型的数据排序**，比如说，可以直接排整型数据，也可以排结构体类型的数据，甚至是字符串数据，通用性极强。这样的排序确定不来学习一下吗？？？

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

## 二、qsort() 函数的参数 ##

![6a51588ef3c64e5796c3eff607e9d0b5.png][]

很明显 qsort()函数具有4个参数，接下来博主来解剖一下这些参数代表着什么意思。

**1. void \* base :** 首先来了解一下什么是 void\* ，这个是无具体类型的指针，void \* 的指针是非常宽容的，可以接收任意类型的数据。常常用来临时存放数据，等到需要使用数据时，我们必须要**强制类型转换**成某一具体类型的数据，才能对数据进行操作。

![62dceba08bd34fc8b18bab2977967b00.png][]

对void \*pa,接收了一个整型 a 的地址，我们对指针pa 进行强制类型转换（int\*），再解引用 pa即可对变量a 进行操作。

void \*base 存的就是待排序数据的起始地址（不能直接访问）。

**这个参数是 qsort() 函数能够对任意数据排序的基础。**

**2. size\_t num :**记录待排序数据元素个数。

**3.** **size\_t size :** 记录待排序数据任意一个元素的所占的字节数（元素的大小）。

**4. int (\*compar) (const void\* , const void\* ) :**

这其实是一个**函数类型的指针**，可以用来存储函数的地址，然后也提前声明了函数的参数，返回值

返回值是 int 类型，参数部分是两个 void \* 类型的接收。这个函数的作用是来比较两个参数的大小，然后返回比较果结，怎么比呢？ 如果是整型数据使两个参数相减，返回结果。如果是字符串，我们可以使用 **strcmp(“字符串”，“字符串”);**strcmp 函数的返回值也是整型数据（这个是根据对应的场景，选择比较方式），即可得到相应的结果。

这第四个参数需要我们自己设计实现，函数的作用就是比较任意两个参数，返回一个整型数据，就可以利用这个数据来判断两个元素大小，所以这是个比较排序。

![3f47ea65658c4e17a741f72f6783dd23.png][]

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

## 三、qsort() 函数的使用 ##

**qsort()函数包含在 stdlib.h库里，所以我在使用前需要申明一下。**

### 3.1 对整型数据排序 ###

#include<stdio.h>
    #include<stdlib.h>//头文件声明
    
    //判断两个元素的大小
    int Compar(void const *p1,void const *p2)//无具体类型的指针接收数据，使用时强制类型转换。
    {
        //两个整型数据相减，即可即可得到三种信息>,<,=
        return (*(int*)p1 - *(int*)p2) *(-1); //利用乘-1改变符号控制升序还是降序
    }
    
    //打印
    void Print(int *arr,int n)
    {
        for (int i=0;i<n;++i)
        {
            printf("%d ",arr[i]);
        }
    }
    
    int main()
    {
        int arr[] = { 8,6,4,2,3,7,1,2,3,10,9 };
        int len = sizeof(arr) / sizeof(arr[0]);//记录数组元素个数
        int size = sizeof(arr[0]);//记录某一个元素的大小所占的字节数
    
        //库函数
        qsort(arr, len, size, Compar);
        //第四个参数，直接传函数的地址，函数名代表函数的地址，由函数指针接收。
    
        //打印
        Print(arr, len);
        return 0;
    }

![3227595bf389482ca07c281118b83560.png][]

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

### 3.2 对结构体类型数据排序 ###

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    typedef struct Student//定义一个Student类型的结构体
    {
    	char name[12]; //姓名
    	int age;       //年龄
    	char StuID[8]; //学号
    }Student;//typedef,重命名一下，简化。
    
    //比较任意两个元素的大小。
    int CmpSort(const void* p1, const void * p2)
    {
    	//return ( ((Student*)p1)->age - ((Student*)p2)->age );//根据年龄来比
    
    	return (strcmp(((Student*)p1)->name,((Student*)p2)->name));//按照姓名的首字母来比较
    }
    
    //打印
    void Print(Student* ps,int n)
    {
    	for (int i=0;i<n;++i)
    	{
    		printf("%s %d %d\n",ps[i].name,ps[i].age,ps[i].StuID);
    	}
    }
    
    int main()
    {
    	Student student[3] = { {"张三",18,"21933321"},{"李四",20,"21933323"},{"王老五",19,"21933322"}};
    
    	int len = sizeof(student) / sizeof(student[0]);//统计Student 类型，student数组的元素的个数
    	int size = sizeof(student[0]);//统计某一个Student 元素所占的字节数。
    	//库函数
    	qsort(student,len,size,CmpSort);
    
    	Print(student,len);//打印
    	
    	return 0;
    }

![c69ca13191ec43d79ec7a5574aaaa346.png][]

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

## 四、快速排模拟实现qsort()函数 ##

好了经过以上三节内容的铺垫，相信大家应该对 **qsort()** 函数的用法，功能明白了，接下来我们就要来模拟实现函数内部。上文说到排序思想是用快速排序的思想。那博主今天就用**快速排序——左右指针法来模拟实现**。**挖坑法**有一点复杂（下文解释）。

老铁如果对快速排序的几种排序思想还有什么不明白的可以学习博主的专栏。文章最后会贴。

什么是左右指针法？一张图带你搞定：

![f3d224c6360f4231b8b3d8a4490e3f8f.png][]

利用递归来继续分割区间，分割后继续单趟排，最后实现整体排序，排序结束。

算法逻辑弄明白了，现在还有一个问题，那就是函数内部，不知道我们要对什么类型的数据进行排序，我们虽然使用 void \* 无指定类型的指针来接收数据，内部怎么根据数据的类型来进行强制类型转换呢？不转换无法处理数据。

大家回忆一下，我们qsort()函数是不是有四个参数，其中有一个参数就是 某一个元素所占的字节大小。size。

我们是不是可以将 void \* 转换成 char \* ，char\* 的指针每一次只能访问一个字节的内容。

举个例子：

![0266d0d4da2644bcab24d06519439399.png][]![34842678efb54a29bb06b9cb272380cb.png][]

现在访问数据元素的问题解决了，那怎么交换数据元素的位置呢？

还是建立在访问元素的基础上，先找到需要交换的元素的位置，再根据 size 的大小一个字节一个字节的交换数据。

//交换数据
    void Swap(char* base1, char* base2, int size)
    {
    	for (int i = 0; i < size; ++i)//按字节转换
    	{
    		char tmp = *base1;
    		*base1 = *base2;
    		*base2 = tmp;
    		++base1;
    		++base2;	
    	}
    }

这一趟下来，两个元素的就实现了交换。

**完整版代码：**

#include <stdio.h>
    #include <stdlib.h>
    
    int Cmp_qsort(void const* p1, void const* p2)//用户输入，
    {
    	int size1 = (*(int*)p1 - *(int*)p2);
    	return size1;
    }
    
    //交换数据
    void Swap(char* base1, char* base2, int size)
    {
    	for (int i = 0; i < size; ++i)//按字节转换
    	{
    		char tmp = *base1;
    		*base1 = *base2;
    		*base2 = tmp;
    		++base1;
    		++base2;	
    	}
    }
    
    //模拟实现
    void _Quick_qsort(void const* base, int left, int right, int size, int(*Cmp_qsort)(void const* p1, void const* p2))
    {
    	if (left >= right)
    	{
    		return;
    	}
    
    	int begin = left;
    	int end = right;
    	int key = begin;//记录坑位的下标、
    
    	while (begin < end)
    	{
    
    		while (begin < end && (Cmp_qsort((char*)base+ key*size, (char*)base + end * size) <= 0))
    			--end;
    
    		while (begin < end && (Cmp_qsort((char*)base+ key*size, (char*)base + begin * size) >= 0))
    			++begin;
    		Swap((char*)base +begin * size, (char*)base+end*size, size);
    
    	}
    	Swap((char*)base + begin * size, (char*)base + key * size, size);
    
    	_Quick_qsort(base, left, begin - 1, size, Cmp_qsort);
    	_Quick_qsort(base, begin + 1, right, size, Cmp_qsort);
    
    }
    
    
    //过渡一下
    void Quick_qsort(void const* base, int len, int size,int(*Cmp_qsort)(void const *p1,void const *p2))
    {
    	_Quick_qsort(base, 0, len - 1, size, Cmp_qsort);//左右区间写入参数，
    }
    
    //打印
    void Print(int* a, int n)
    {
    	for (int i = 0; i < n; ++i)
    	{
    		printf("%d ", a[i]);
    	}
    }
    
    //快排左右指针法
    int main()
    {
    	int a[] = {6,1,2,10,7,9,9,3,4,5,10,8};
    	int len = sizeof(a) / sizeof(a[0]);
    	int size = sizeof(a[0]);
    
    	Quick_qsort(a, len, size,Cmp_qsort);//快速排序模拟实现
    
    	Print(a, len);//打印
    	return 0;
    
    }

![7ba1adcf1b034c95977259f4f87b7166.png][]

这个模拟是争对于顺序结构的数据，而链式结构要采用不同的办法。

> 不采用快排的挖坑发的原因是：我们需要一个类型大小的空间存坑值，这个时候我们只能根据size（一个元素所占的字节数）动态开辟一个char \*的数组，一个字节一个字节的存储。如果光定义指针指向，那坑值指针，会随着指向地址的元素的变化而变化。

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

至此，C语言的深度解剖 qsort() 函数，博主已经分享完了，希望对大家有所帮助，如有不妥之处欢迎批评指正。

![40e36dfc27804c04afb4a9da45afda94.jpeg][]

本期收录于博主的专栏——数据排序，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“经典数据排序”。[排序算法\_保护小周ღ的博客][Link 1]

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ **\*★,°\*:.☆(￣▽￣)/$:\*.°★\***

文章存在借鉴，如有侵权请联系修改删除！ ![dd8b4788b2554df4bec4b8202395cad2.gif][]

[30adcf5df8b44dc8bc660f667cada2c4.jpeg]: https://img-blog.csdnimg.cn/30adcf5df8b44dc8bc660f667cada2c4.jpeg
[f89deef4fd5b408f8b4b1c0a50c0a9e9.png]: https://img-blog.csdnimg.cn/f89deef4fd5b408f8b4b1c0a50c0a9e9.png
[8b354a7916f240d0bc7839822301ba90.gif_pic_center]: https://img-blog.csdnimg.cn/8b354a7916f240d0bc7839822301ba90.gif#pic_center
[6a51588ef3c64e5796c3eff607e9d0b5.png]: https://img-blog.csdnimg.cn/6a51588ef3c64e5796c3eff607e9d0b5.png
[62dceba08bd34fc8b18bab2977967b00.png]: https://img-blog.csdnimg.cn/62dceba08bd34fc8b18bab2977967b00.png
[3f47ea65658c4e17a741f72f6783dd23.png]: https://img-blog.csdnimg.cn/3f47ea65658c4e17a741f72f6783dd23.png
[3227595bf389482ca07c281118b83560.png]: https://img-blog.csdnimg.cn/3227595bf389482ca07c281118b83560.png
[c69ca13191ec43d79ec7a5574aaaa346.png]: https://img-blog.csdnimg.cn/c69ca13191ec43d79ec7a5574aaaa346.png
[f3d224c6360f4231b8b3d8a4490e3f8f.png]: https://img-blog.csdnimg.cn/f3d224c6360f4231b8b3d8a4490e3f8f.png
[0266d0d4da2644bcab24d06519439399.png]: https://img-blog.csdnimg.cn/0266d0d4da2644bcab24d06519439399.png
[34842678efb54a29bb06b9cb272380cb.png]: https://img-blog.csdnimg.cn/34842678efb54a29bb06b9cb272380cb.png
[7ba1adcf1b034c95977259f4f87b7166.png]: https://img-blog.csdnimg.cn/7ba1adcf1b034c95977259f4f87b7166.png
[40e36dfc27804c04afb4a9da45afda94.jpeg]: https://img-blog.csdnimg.cn/40e36dfc27804c04afb4a9da45afda94.jpeg
[Link 1]: https://blog.csdn.net/weixin_67603503/category_11904303.html?spm=1001.2014.3001.5482
[dd8b4788b2554df4bec4b8202395cad2.gif]: https://img-blog.csdnimg.cn/dd8b4788b2554df4bec4b8202395cad2.gif