一.qsort()函数的基本信息及功能

我们日常生活中经常能碰到需要给一组数据排序的情况，如将班上同学的身高从大到小排序，将淘宝上的商品价格从低到高排序，将班上的同学姓名按首字母顺序排序......随着科学技术的发展，现在这些工作完全可以交给excel一键完成，那么电脑是根据什么程序完成这些排序的？

接下来我们就来给大家介绍一下C语言库函数中可以“给万物排序”的qsort()函数：

先来看一下qsort()函数（quick sort）在百度百科中的定义​

因此，qsort()函数是一个C语言编译器函数库自带的排序函数，它可以对指定数组（包括字符串，二维数组，结构体等）进行排序。

二.常见的排序算法及冒泡排序

我们熟知的数组排序的算法有很多，如冒泡排序，选择排序，直插排序，希尔排序，并归排序，快速排序等，具体八大算法的实现可以移步这篇博客【数据结构】八大排序算法

了解了这些种类繁多的排序算法后，我们希望能够使用一种较为简单的排序算法来实现qsort函数的功能，来模拟实现同样具有可以排序数组，字符串，结构体功能的排序函数。如，我们可以使用冒泡排序的算法来实现具有排序字符串，二维数组，结构体等功能的bubble_sort()函数。

如果还有不太熟悉冒泡排序的朋友可以移步这篇博客【C语言】冒泡排序详解 ，里面有关于冒泡算法完全0基础的详解，这里就不多赘述了，我们在这里直接演示一下冒泡排序的用法：

冒泡排序算法演示（以升序为例）：

数组元素初始顺序如下：

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

冒泡排序（升序）运行结果：​

 冒泡排序（升序）完整代码如下：

//冒泡排序<升序>
#include<stdio.h>
void print(int arr[])
{
	int i = 0;
	for (i = 0; i <= 9; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void sort(int arr[],int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for(j=0;j<sz-1-i;j++)
		{	
			if (arr[j] > arr[j + 1])
			{
				int emp =arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = emp;
			}
		}
	}
}
 
int main()
{
	int arr[10] = { 3,1,5,9,7,6,4,8,0,2 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	print(arr);
	sort(arr,sz);
	print(arr);
	return 0;
}

三.逐一解读qsort()函数的参数及其原理

在搞清了我们的排序算法后，接下来为了进一步模仿实现qsort()函数，我们需要逐一解读qsort()函数的参数及其作用，以便后续模仿实现它。

从cplusplus官网（cplusplus（C语言函数查询网站） ）上我们可以看到qsort()函数是有四个参数的，如图：​

 而cplusplus官网对这四个变量的解释是：​

接下来我们一起来分析一下这四个参数及其作用：

1.void* base

void* base

​

即，qsort()函数需要的第一个参数是待排序数组的首元素地址，而void*的意思是它是一个无类型指针，而无类型的原因是我们希望它是一个可以排序很多种类数据的排序函数，如果这里的指针类型固定，我们就只能对函数传入固定类型的参数进行排序了。

因此，要让qsort()函数帮助我们排序，首先要告诉它这组数据的首地址在哪。

2.size_t num

size_t num

​

这个参数代表待排数组的元素个数。且因为元素个数恒为非负数，因此该参数的数据类型是size_t(即无符号整形)。

计算数组元素个数常用的是sizeof,即数组元素个数=数组总长度/数组首元素长度，如：

size_t num=sizeof(arr)/sizeof(arr[0]);

因此，要让qsort()函数帮助我们排序，我们还要告诉它这个数组一共有多少个元素。

3.size_t size

size_t size

 该参数意为待排数组中每个元素的长度。同样因为元素长度恒为非负数，因此参数的数据类型是size_t(无符号整形)。

计算数组元素长度常用sizeof,及数组每个元素长度=数组首元素的长度，如：

size_t size=sizeof(arr[0]);

因此，要让qsort()函数帮助我们排序，我们还要告诉它这个数组中的每个元素的长度（即首元素的长度）。

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

int (*compar)(const void*,const void*)

这个应该算最难理解的部分了，不过我们一点一点来看，还是先画个图帮助大家理解吧：​

 经过我们的分析可知，该参数是一个函数指针，该指针指向的函数需要两个无类型的指针作为参数，同时该函数的返回值是一个int类型的整形。

他的作用是将传进来的两个参数进行比较，如果参数p1<参数p2，则返回一个小于0的数，如果参数p1=参数p2,则返回0；如果参数p1>p2，则返回一个大于0的数。

注意！compar()函数的作用仅仅是比较两个参数的大小，并通过返回值的形式告诉qsort()函数比较的结果，在运行期间是不能更改参数1或参数2的值的，所以为保险起见，我们可以给两个参数前加上const修饰，来使参数指向的数值无法改变。

小tips:const修饰的指针，在*符号左边即为固定指向的值不可改变，在*符号右边则为固定指针指向的方向不可改变。可以简记为：左定值，右定向。​

compar()函数编写样例如下：​

需要注意的是：这个指针指向的函数是由你自己编写的，即qsort()函数会在其内部调用你编写的比较函数，而这个比较函数如何比较qsort()函数传递的两个参数是完全由你自己定义的。

在qsort()函数调用完compar()函数后，会接收到compar()返回的一个有符号的整型数字，当接收到comper()返回大于0的数字时，qsort()函数就会将这两个元素做交换。而如果接收到comper()函数返回小于等于0的数时，qsort()函数不对其进行交换。

因此，在compar()函数使用*p1-*p2的方式直接返回结果数字时，qsort()排出的序默认会是升序。而如果你希望qsort()函数排出一个降序数组时，那么就需要调换一下*p1和*p2的减法关系，直接返回*p2-*p1的值即可。

下面列举一些大家常用的compar()比较函数：

1.对一维数组进行排序

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

2.对二维数组进行排序

int comper(const void*a,const void*b)
{
return((int*)a)[0]-((int*)b)[0];
}

3.对字符串进行排序

int comper(const void*p1,const void*p2)
{
return strcmp((char*)p2,(char*)p1);
}

4.按结构体中某个关键字排序（对结构体一级排序）：

structNode
{
double data;
int other;
}s[100];

int comper(constvoid*p1,constvoid*p2)
{
return(*(Node*)p2).data>(*（Node*）p1).data?1:-1;
}

5.对结构体中字符串进行排序：

struct Node
{
int data;
char str[100];
}s[100];

//按照结构体中字符串str的字典序排序
int comper(const void*p1,const void*p2)
{
return strcmp((*(Node*)p1).str,(*(Node*)p2).str);
}

四.使用qsort()函数完成整形，结构体的排序（演示）

了解了qsort()函数的参数及其原理后，我们来尝试使用它完成一些排序任务，以此来熟悉qsort()函数的使用方法。

1.使用qsort()函数完成对一维整形数组的排序：

要使用qsort()函数，就要先准备好它需要的四个参数，即数组的首地址，数组的长度，数组每个元素的长度，还有比较函数的地址（即函数名）。我们依次准备好这四个参数：
​

​

 接下来就可以调用qsort()函数查看结果了：​

 可以看到，qsort()函数成功帮我们将该组整形排列成了升序。该部分完整代码如下：

//使用qsort()函数排序一维数组
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

int compar(const void* p1, const void* p2)
{
return ((*(int*)p1) - (*(int*)p2));
}

int main()
{
    int arr[10] = { 3,1,5,9,7,6,4,8,0,2 };
    size_t num = sizeof(arr) / sizeof(arr[0]);
    size_t sz = sizeof(arr[0]);
    qsort(arr, num, sz, compar);

    int i=0;
    for (i = 0; i < num; i++)
        printf("%d ", arr[i]);

    return 0;
}

2.使用qsort()函数完成对结构体的排序：

要使用qsort()函数排序结构体，我们首先要创建一个结构体变量，如下，我们先创建一个包含人名和年龄的结构体变量：​

 下面会以这个结构体变量为例，分别实现使用qsort()函数完成对结构体按年龄和按姓名的排序。

1>.使用qsort()函数完成对结构体按年龄排序

我们照例先准备好它需要的四个参数，即结构体的首地址，结构体的长度，结构体每个元素的长度，还有比较函数的地址。我们依次准备好这四个参数：

​

​

 接下来就可以调用qsort()函数查看结果了：​

 可以看到，qsort()函数帮助我们将该结构体成功按年龄从小到大重新排序了。该部分完整代码如下：

//使用qsort()函数按年龄排序结构体
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//创建结构体
struct Stu
{
    char name[20];
    int age;
};

//compar_按年龄排序
int compar_Stu_age(const void* p1, const void* p2)
{
    return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}

int main()
{
    struct Stu s[3] = { {"zhangsan",20} ,{"lisi",30},{"wangmazi",25} };
    size_t num = sizeof(s) / sizeof(s[0]);
    size_t sz = sizeof(s[0]);
    qsort(s, num, sz, compar_Stu_age);
    for (int i = 0; i < 3; i++)
    {
        printf("%s,%d\n", s[i].name, s[i].age);
    }

    return 0;
}

2>.使用qsort()函数完成对结构体按姓名排序

我们照例先准备好它需要的四个参数，即结构体的首地址，结构体的长度，结构体每个元素的长度，还有比较函数的地址。我们依次准备好这四个参数：

​

​

需要特别注意按姓名排序的排序函数，因为按姓名排序本质上是给字符串排序，所以我们借助strcmp()函数来比较两个字符串的大小，并将比较的结果返回给qsort()函数。

有关strcmp()函数的相关信息如下：

 接下来就可以调用qsort()函数查看结果了：

 可以看到，qsort()函数按照名字顺序（字典序）帮助我们成功排好了结构体的顺序，该部分完整代码如下：

//使用qsort()函数按姓名排序结构体
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//创建结构体
struct Stu
{
    char name[20];
    int age;
};

//compar_按姓名排序
int compar_Stu_name(const void* p1, const void* p2)
{
    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}

int main()
{
    struct Stu s[3] = { {"zhangsan",20} ,{"lisi",30},{"wangmazi",25} };
    size_t num = sizeof(s) / sizeof(s[0]);
    size_t sz = sizeof(s[0]);
    qsort(s, num, sz, compar_Stu_name);

//打印结果
    for (int i = 0; i < 3; i++)
    {
        printf("%s,%d\n", s[i].name, s[i].age);
    }

    return 0;
}

 五.套用冒泡排序算法，改造并模拟实现qsort()函数

通过上面的例子，我们已经能够熟练使用并足够了解qsort()函数了，接下来我们就可以尝试套用冒泡算法来试试实现bubble_sort()函数了：

1.bubble_sort()函数定义及参数

函数参数没什么好说的，因为要模拟实现qsort()函数，因此直接仿照qsort()函数的参数即可：

void bubble_sort(void*base, size_t num,size_t sz,int(*compar)(const void*,const void*))

2.bubble_sort()函数函数体

函数体内部逻辑整体参考冒泡排序，只在一小部分地方有略微的改动。首先因为我们在整个bubble_sort()函数中都不知道base传进的参数到底是什么类型的，因此索性不去纠结数据的类型，干脆将他们统一视为一个字节一个字节的空间来进行比较及交换，因此传入bubble_sort()函数的指针统一强制类型转换成char*类型，以便后续我们一个字节一个字节操作。该部分代码及解析如下：

{
    size_t i = 0;
    for (i = 0; i < num - 1; i++)
    {
        size_t j = 0;
        for (j = 0; j < num - 1 - i; j++)
        {
            if (compar((char*)base+j*sz,(char*)base+(j+1)*sz) > 0)
//因为无法确定base到底代表什么类型的指针，因此不如全部当作字符（只占1字节）指针来处理
            {
                //交换
                Swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
//交换思路同样是一个字节一个字节交换
            }
        }
    }
}

3.bubble_sort()函数中的回调函数Swap()

我们把原本冒泡排序中的交换步骤直接重新分装成一个函数，专门用来交换比较后需要交换的两个元素，同样因为我们并不知道该数据的类型，只知道该数据的大小sz，因此我们不如直接将两个sz大小的字节内容逐个一个字节一个字节逐一交换，这样就能保证不论是什么类型的数据，交换完都不会出现差错了。该部分代码如下：

//交换函数
void Swap(char* buf1, char* buf2,int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}

六.使用bubble_sort()函数完成整形，结构体的排序（演示）

完成了bubble_sort()函数的编写，接下来我们尝试使用它来代替前面的qsort()函数给数组及结构体进行排序：

1.使用bubble_sort()函数完成对一维整形数组的排序

我们像之前使用qsort()那样准备好bubble_sort()所需要的四个参数：

​

​

接下来就可以使用bubble_sort()函数查看结果了：​

 可以看到，bubble_sort()函数按照整形大小帮我们排好了升序。该部分完整代码如下：

//使用冒泡排序排列一维数组
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

void Swap(char* buf1, char* buf2,int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}

void bubble_sort(void*base, size_t num,size_t sz,int(*compar)(const void*,const void*))
{
    size_t i = 0;
    for (i = 0; i < num - 1; i++)
    {
        size_t j = 0;
        for (j = 0; j < num - 1 - i; j++)
        {
            if (compar((char*)base+j*sz,(char*)base+(j+1)*sz) > 0)
            {
                Swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
            }
        }
    }
}

int compar(const void* p1, const void* p2)
{
    return ((*(int*)p1) - (*(int*)p2));
}

int main()
{
    int arr[10] = { 3,1,5,9,7,6,4,8,0,2 };
    size_t num = sizeof(arr) / sizeof(arr[0]);
    size_t sz = sizeof(arr[0]);

    bubble_sort(arr, num, sz, compar);
    
    int i = 0;
    for (i = 0; i < num; i++)
        printf("%d ", arr[i]);
    return 0;
}

2.使用bubble_sort()函数完成对结构体的排序

要使用bubble_sort()函数排序结构体，我们首先要创建一个结构体变量，如下，我们先创建一个包含人名和年龄的结构体变量：

 下面会以这个结构体变量为例，分别实现使用bubble_sort()函数完成对结构体按年龄和按姓名的排序。

1>.使用bubble_sort()函数完成对结构体按年龄排序

我们照例先准备好它需要的四个参数，即结构体的首地址，结构体的长度，结构体每个元素的长度，还有比较函数的地址。我们依次准备好这四个参数：

​

接下来就可以调用bubble_sort()函数查看结果了：​

 可以看到，bubble_sort()函数帮助我们将该结构体成功按年龄从小到大重新排序了。该部分完整代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

//交换函数
void Swap(char* buf1, char* buf2, int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}

void bubble_sort(void* base, size_t num, size_t sz, int(*compar)(const void*, const void*))
{
    size_t i = 0;
    for (i = 0; i < num - 1; i++)
    {
        size_t j = 0;
        for (j = 0; j < num - 1 - i; j++)
        {
            if (compar((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
            {
                Swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
            }
        }
    }
}

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

//compar_按年龄排序
int compar_Stu_age(const void* p1, const void* p2)
{
    return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}

int main()
{
    struct Stu s[3] = { {"zhangsan",20} ,{"lisi",30},{"wangmazi",25} };
    size_t num = sizeof(s) / sizeof(s[0]);
    size_t sz = sizeof(s[0]);

    bubble_sort(s, num, sz, compar_Stu_age);

    for (int i = 0; i < 3; i++)
    {
        printf("%s,%d\n", s[i].name, s[i].age);
    }
    return 0;
}

 2>.使用bubble_sort()函数完成对结构体按姓名排序

我们照例先准备好它需要的四个参数，即结构体的首地址，结构体的长度，结构体每个元素的长度，还有比较函数的地址（即函数名）。我们依次准备好这四个参数：

​

​

 接下来就可以调用bubble_sort()函数查看结果了：​

可以看到，bubble_sort()函数按照名字顺序（字典序）帮助我们成功排好了结构体的顺序，该部分完整代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//交换函数
void Swap(char* buf1, char* buf2, int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        char tmp = *buf1;
        *buf1 = *buf2;
        *buf2 = tmp;
        buf1++;
        buf2++;
    }
}

void bubble_sort(void* base, size_t num, size_t sz, int(*compar)(const void*, const void*))
{
    size_t i = 0;
    for (i = 0; i < num - 1; i++)

    {
        size_t j = 0;
        for (j = 0; j < num - 1 - i; j++)
        {
            if (compar((char*)base + j * sz, (char*)base + (j + 1) * sz) > 0)
            {
                Swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);
            }
        }
    }
}

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

//compar_按姓名排序
int compar_Stu_name(const void* p1, const void* p2)
{
    return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}

int main()
{
    struct Stu s[3] = { {"zhangsan",20} ,{"lisi",30},{"wangmazi",25} };
    size_t num = sizeof(s) / sizeof(s[0]);
    size_t sz = sizeof(s[0]);

    bubble_sort(s, num, sz, compar_Stu_name);

    for (int i = 0; i < 3; i++)
    {
        printf("%s,%d\n", s[i].name, s[i].age);
    }
    return 0;
}

七.qsort()的核心:快速排序算法

快速排序的思想

快排算法的基本思想是:

• 通过一趟排序将待排数据分割成独立的两部分

• 其中一部分数据的关键字均比另一部分数据的关键字小

• 可分别对这两部分数据继续进行排序,以达到整个序列有序的目的.

具体的快速排序算法是如何实现的,我放在另一篇博客中了,里面不仅有三种实现快排算法的方式,并且包含了如何使用非递归方式实现快排算法,这里有于篇幅有限,就不对赘述了,感兴趣的朋友可以移步这篇博客:

【数据结构】八大排序之快速排序算法 

总结

以上就是关于qsort()函数及其模拟实现bubble_sort()函数的全部内容，希望能对大家有所帮助或有所启发,欢迎各位大佬在评论区或私信与我交流.