目录

  • 一、qsort函数介绍
  • 二、qsort函数参数介绍
    • 2.1：void* base
    • 2.2：size_t num
    • 2.3：size_t size
    • 2.4：int(* compar)(const void *,const void *)
  • 三、实际应用
    • 3.1：利用qsort函数对整型数组排序
    • 3.2：利用qsort函数对结构体数组排序
  • 四、利用冒泡排序模拟实现qsort函数
    • 4.1：冒泡排序
    • 4.2：模拟实现qsort函数
    • 4.3：实际应用
      • 4.3.1：利用bulle_sort函数对整型数组排序：
      • 4.3.2：利用bulle_sort函数对结构体数组排序：

一、qsort函数介绍

 qsort是一个库函数，可以对任意数据类型的数组进行排序。它的底层是通过快速排序来实现的
cplusplus网站中对qsort函数的解释如下：

qsort的函数声明：

 void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

qsort函数的参数：

  • void* base
  • size_t num
  • size_t size
  • int(*compar)(const void*,const void*)

qsort函数的返回值：
qsort函数的返回值void型

二、qsort函数参数介绍

2.1：void* base

 参数base的类型是void*（空指针），说明base是一个指针，它指向待排序数组的第一个元素，换言之：base存放的是待排序数组的首元素地址

补充：void*类型介绍：
void*是无具体指向的指针类型，任何类型变量的地址都可以存放到void型指针变量里面，这可以说是void*变量的一个优点。当然它也有一个致命的缺点：void*指针不能解引用。

为什么base的类型是void*呢” />2.2：size_t num

 num中存的是待排序数组的元素个数，他的类型是size_t，size_t其实就是把unsigned int重命名的得到的。

2.3：size_t size

 size中存的是数组中每个元素的大小（以字节为单位）。

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

 compar是一个函数指针类型，所谓函数指针就是可以指向一个函数，里面存放的是函数的地址。

compar到底指向什么函数呢?
compar是英文单词compare（比较）的缩写，所以顾名思义，compar是比较的意思，说明它指向一个比较函数。

什么是比较函数？
要实现对数组元素的排序，那一定要对数组里面的元素进行逐一比较，而对于不同类型的数组来说，它们的比较方法也有所不同。比如：整型数组可以比较它们元素之间的大小关系，而字符数组则有专门的字符串比较函数strcmp，如果是一个结构体数组，一个结构体里面有不同的数据，我们就可以按照不同的标准进行排序。就像对一群人进行排序，可以按照年龄排，也可以按照身高排等等。此时就需要用户自己确定一个排序的标准，用函数封装起来，然后把这个函数的地址传给qsort函数用函数指针compar来接收。

对比较函数的要求：
形参compar已经规定了它所指向的函数类型是：int (const void*,const void).即：所指向的比较函数有两个void*类型的参数，函数的返回值是int型。

比较函数的参数、返回值的意义：
int compar (const void* p1, const void* p2);
其中两个void*类型的参数 p1 和 p2 用来存放数组中待比较的两个元素的地址。如果compar函数的返回值小于0，会把p1指向的元素排到p2指向的元素前面；如果返回值等于0，不会改变p1和p2指向的元素位置；如果返回值大于0，会把p1指向的元素排到p2指向的元素后面。

三、实际应用

3.1：利用qsort函数对整型数组排序

int comper(const void* e1, const void* e2)//comper函数是用户自己写的，我们自己当然知道要排序的元素类型是什么//我们就可以利用强制类型转化来实现对e1和e2的比较{return *(int*)e1 - *(int*)e2;//void*类型不能直接解引用}//*(int*)e1 - *(int*)e2<0//说明e1指向的元素比e2指向的元素小，此时刚好返回一个小于0的数，qsort就会把e1指向的元素排在e2指向的元素前面//*(int*)e1 - *(int*)e2>0//说明e1指向的元素比e2指向的元素大，此时刚好返回一个大于0的数，qsort就会把e2指向的元素排到e1指向的元素前面int main(){int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), comper);//利用库函数qsort来排序int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");return 0;}//结果：0 1 2 3 4 5 6 7 8 9

3.2：利用qsort函数对结构体数组排序

按照年龄排序：

struct Stu{char name[20];int age;};//根据名字比较int comper_age(const void* e1, const void* e2){return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}int main(){struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;//排序前打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");//根据年龄进行排序qsort(arr, sz, sizeof(arr[0]), comper_age);//排序后打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");return 0;}//结果：zhangsan 100 lisi 20 wangwu 3wangwu 3 lisi 20 zhangsan 100

按照名字进行排序：

struct Stu{char name[20];int age;};//按照名字比较int comper_name(const void* e1, const void* e2){return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e1)->name);//名字是字符串，所以名字的比较要用到字符串比较 函数strcmp}int main(){struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;//排序前打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");//按照年龄进行排序qsort(arr, sz, sizeof(arr[0]), comper_name);//排序后打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");return 0;}//结果：zhangsan 100 lisi 20 wangwu 3lisi 20 wangwu 3 zhangsan 100

四、利用冒泡排序模拟实现qsort函数

4.1：冒泡排序

 关于冒泡排序的详细讲解可以参考我的这篇文章：初级C语言之【数组】里面详细介绍了冒泡排序

//冒泡排序函数void bulle_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 tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}}int main(){int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bulle_sort(arr,sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;}//结果：0 1 2 3 4 5 6 7 8 9

缺陷1：
用来接收待排序数组首元素地址的指针arr已经被写死了，是int*型，说明只能对整型数组进行排序

缺陷2：

缺陷2如上图所示，红色方框框起来的部分只适用于对整数之间的大小关系进行比较，然后交换

4.2：模拟实现qsort函数

//利用冒泡排序模拟实现qsortvoid Swap(char* ele1, char* ele2,int width){int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}}void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收//第二个参数 - 用来接收数组元素个数//第三个参数 - 用来接收数组元素的宽度{size_t i = 0;//趟数for (i = 0; i < sz - 1; i++){//一趟冒泡的过程size_t j = 0;for (j = 0; j < sz-1-i; j++){if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)//把arr强转为char*，arr就可以正常使用//char类型指针+1只会跳过一个字节//+j*width表示跳过j个元素{//交换//由于这里的数组名已经被转为char类型的指针//所以要交换数组中的元素，就只能一个字节一个字节进行交换Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);//前两个参数是待交换元素的地址，第三个参数是元素的宽度}}}}

 这里说的利用冒泡排序来实现qsort函数，仅仅是实现了qsort函数可以对任意类型的数组进行排序这一特点，并不是说实现qsort函数的底层原理，qsort的底层是通过快速排序来实现的。
因此，为了使改变之后的冒泡函数能够对任意类型的数组进行排序，原本冒泡排序函数的参数就要发生改变，和qsort函数一样，新的冒泡排序函数也要有以下4个参数：

  • void* arr
  • size_t sz
  • size_t width
  • int(*comper)(const void*e1,const void*e2)

 arr用来接收待排序数组首元素的地址，sz用来接收待排序数组的元素个数，width用来接收数组中每个元素的大小（单位是字节），comper用来接收比较函数的地址。参数的改变解决了原冒泡排序函数的缺陷1。
接下来要解决原冒泡排序函数的缺陷2，缺陷2的主要问题在于它的普适性不够强，首先要对交换的判断条件，即if后面的判断语句做出改变，让他能够比较任意两个类型的数据，这时，比较函数就发挥作用了，我们只需要把待比较的两个元素地址传给比较函数，由比较函数来判断它们之间的关系
新的问题又出现了，comper函数的形参需要接收两个待比较元素的地址，这里的待比较元素一定是当前待排序数组里面的元素，但是待排序数组的首元素地址是用空指针（void*）来接收的，无法直接使用，这意味着现在无法通过数组首元素的地址，顺藤摸瓜去访问数组中的元素。这里问题的关键就是空指针无法使用，那我们就想到把空指针进行强制类型转化，把空指针变成有具体指向的指针不就可以正常使用了，问题又出现了，有那么多的指针类型，到底把空指针强转成什么类型的指针呢？？？答案是：把空指针强转成字符指针（char*）。这里是因为，字符指针+1仅跳过一个字节，我们可以通过改变加数的数值，使指针指向任意内存空间，这也就意味着强转后的arr指针可以存放任意内存单元的地址，并且可通过地址去访问内存中的数据。

  • (char*)arr+j*width

 这里先把arr指强制类型转化成char*类型，这里的加数是：j*width。其中width表示当前数组中每个元素的大小（单位是字节），这里的+j*width就是跳过j*width个字节，由于width是一个元素的字节，所以+j*width也就意味着跳过了j个元素，此时 (char*)arr+j*width就表示下标为j的元素的地址。

  • (char*)arr+(j+1)*width

 同理(char*)arr+(j+1)*width就表示下标为j+1的元素的地址。

 此时就可以把待比较的两个元素的地址传给用户自己写的comper函数了，通过comper函数的返回值来判断这两个元素是否要交换。

 到这里缺陷2中的问题只解决了一半，即：只把交换的判断条件做了修改，增强了交换判断条件的普适性，使其可以对任意类型的数组中的元素进行比较。具体的交换步骤还没有修改，当前的交换步骤仅仅适用于整型数据。根据经验，对两个变量进行交换，需要创建一个中间变量，比如：交换两个整型变量，需要创建一个整形的中间变量；交换两个字符型变量，需要创建一个字符型的中间变量……可见，对于不同类型的数据元素，在交换时创建的中间变量的类型也是不同的，由于无法预知要交换数据的类型，所以也无法提前确定中间变量的类型。这里的解决方案是：一个字节一个字节的交换，这样中间变量的类型就能确定下来了，即为char型。不同的数据类型对应着不同的字节数，但是它们都是由字节组成，我们有了数组中每个元素的字节大小时，就可以写一个循环，从元素的首个字节开始，一个字节一个字节的交换，直到最后一个字节。这里我们写了一个交换函数Swap

  • void Swap(char* ele1, char* ele2,int width)

 Swap函数有三个参数，ele1和ele2分别用来接收待交换的两个元素的地址，width用来接收数组中每个元素的大小（单位是字节）。

void Swap(char* ele1, char* ele2,int width){int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}}

 到此，原来冒泡排序中的两个缺陷已经被成功地解决，经过改造后的冒泡函数bulle_sort就可以对任意类型数组进行排序。

4.3：实际应用

4.3.1：利用bulle_sort函数对整型数组排序：

//利用冒泡排序模拟实现qsort//交换函数void Swap(char* ele1, char* ele2,int width){int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}}//改造后的冒泡排序函数void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收//第二个参数 - 用来接收数组元素个数//第三个参数 - 用来接收数组元素的宽度{size_t i = 0;//趟数for (i = 0; i < sz - 1; i++){//一趟冒泡的过程size_t j = 0;for (j = 0; j < sz-1-i; j++){if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)//把arr强转为char*，arr就可以正常使用//char类型指针+1只会跳过一个字节//+j*width表示跳过j个元素{//交换Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);//前两个参数是待交换元素的地址，第三个参数是元素的宽度}}}}//比较函数int comper_int(const void* e1, const void* e2){return *(int*)e1 - *(int*)e2;}//主函数int main(){int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bulle_sort(arr, sz, sizeof(arr[0]), comper_int);//调用bulle_sort来排序int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");return 0;}//结果：0 1 2 3 4 5 6 7 8 9

4.3.2：利用bulle_sort函数对结构体数组排序：

按照年龄排序：

//利用冒泡排序模拟实现qsort//交换函数void Swap(char* ele1, char* ele2,int width){int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}}//改造后的冒泡排序函数void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收//第二个参数 - 用来接收数组元素个数//第三个参数 - 用来接收数组元素的宽度{size_t i = 0;//趟数for (i = 0; i < sz - 1; i++){//一趟冒泡的过程size_t j = 0;for (j = 0; j < sz-1-i; j++){if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)//把arr强转为char*，arr就可以正常使用//char类型指针+1只会跳过一个字节//+j*width表示跳过j个元素{//交换Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);//前两个参数是待交换元素的地址，第三个参数是元素的宽度}}}}//声明一个结构体struct Stu{char name[20];int age;};//按照年龄进行比较int comper_age(const void* e1, const void* e2){return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}//主函数int main(){struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;//排序前打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");//按照年龄进行排序bulle_sort(arr, sz, sizeof(arr[0]), comper_age);//排序后打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");return 0;}//结果：zhangsan 100 lisi 20 wangwu 3wangwu 3 lisi 20 zhangsan 100

按照名字排序：

//利用冒泡排序模拟实现qsort//交换函数void Swap(char* ele1, char* ele2,int width){int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}}//改造后的冒泡排序函数void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))//第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收//第二个参数 - 用来接收数组元素个数//第三个参数 - 用来接收数组元素的宽度{size_t i = 0;//趟数for (i = 0; i < sz - 1; i++){//一趟冒泡的过程size_t j = 0;for (j = 0; j < sz-1-i; j++){if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)//把arr强转为char*，arr就可以正常使用//char类型指针+1只会跳过一个字节//+j*width表示跳过j个元素{//交换Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);//前两个参数是待交换元素的地址，第三个参数是元素的宽度}}}}//声明一个结构体struct Stu{char name[20];int age;};//按照名字比较int comper_name(const void* e1, const void* e2){return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//名字是字符串，所以名字的比较要用到字符串比较 函数strcmp}//主函数int main(){struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;//排序前打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");//按照名字进行排序bulle_sort(arr, sz, sizeof(arr[0]), comper_name);//排序后打印for (i = 0; i < sz; i++){printf("%s %d ", arr[i].name, arr[i].age);}printf("\n");return 0;}//结果：zhangsan 100 lisi 20 wangwu 3lisi 20 wangwu 3 zhangsan 100