qsort:我很强，了解一下（详解过程）

了解qsort，以及模拟实现

🎑情境引入

struct student
{char name[10];int age;};

你是否有过这样的经历，在对结构体成员进行排序，需要写几个排序，而感到不耐烦呢。
就比如对上面的结构体数组排序，既要对成员name排序，又要对成员age排序。
看了这篇博客，你就可以告别大段落式的排序啦。
qsort表示它很强，它来拯救你了~~❤

qsort强在哪呢？
强在它可以对任意类型的排序（存储结构需要限定–顺序存储）
也就是说qsort只能对顺序存储的结构进行排序。
顺序存储结构有：1.数组，2.在堆区开辟一段连续的空间

🎈qsort

📖qsort的头文件

#include<stdlib.h>

📄开场

qsort底层原理是快排，但在这篇博客中不讲快排，而是讲冒泡排序，以及插入排序去模拟qsort的功能。

为啥还要讲插入排序呢，如果你想对单链表进行排序的话，qsort是不能达到目的的，对于单链表的排序，需要用插入排序的思想进行排序。

通过插入排序模拟qsort，再对存储复杂数据的单链表排序的时候，会轻松很多。

🔑qsort的参数

size_t 是 unsigned int 重命名后的类型名

🤔为什么可以对任意类型排序呢？

主要是在设置函数参数的时候，使用的是void。
void 有个特点，叫“有容乃大”。
void* 可以接收任意类型的指针
同样的任意类型的指针也可以接收void*

在void* 修饰的变量接收任意类型的指针的情况下，该变量是不能进行任何操作的。

因为对指针进行操作是看指针的类型，该变量的类型是void* 。
因为void类型大小是不确定的（vs下0，linux下1）。
那么对该变量进行*或者加减整数操作是没有意义的
指针类型的意义不记得的点这

那如何解决呢？只需要通过强制类型转换即可。

📜参数

参数①

对于参数①

void* base

通过void* 就能够推测一些东西了。void*是指针，是用来接收地址的。
那么在调用qsort的时候，第一个实参一定是个地址。这样理解是没错的，也确实如此。
实参传①就是你想要排序数组的起始地址（或者在堆区开辟空间的起始地址）

参数②

对于参数②

size_t num

，表示你需要排序的数组有多少个元素个数

参数③

对于参数③

size_t size

，表示待排序数组元素的大小（单位是字节）
为什么需要传元素的大小呢？也很好理解，我们需要对不同类型的元素进行排序，不同的类型，所占空间的大小是不同的，如果不传元素的大小，qsort又怎么能对不同类型元素进行排序呢？所以必须传。

最难的参数④

参数④

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

这也是我们能够比较任意类型的关键！
有人看到这个参数感觉头皮发麻，不知道这是啥。先来分析一下。
我们先把中间部分换个形式

int fun (const void*, const void*))

这是啥？这是一个函数！
函数名是

fun

形参为

(const void*, const void*)

返回类型为

int

在回过头来分析

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

，那这是什么？这是指针，因为操作符*，并且与()优先结合，所以是指针。
再结合上面所说，这个指针指向的是一个函数。

有人可能难以理解指向的是函数，那我再说说，请问函数有地址吗？答案是有的。

在多说几嘴，函数名也是可以直接表示函数的地址，也可以不用&。

已经知道函数是有地址的了，那指针去指向一个函数，也就没什么问题的了。看下面这段话，再去理解一番。

看这个表达式

int* p

。
p指向谁？如果你不知道怎么看的话，把指针名p和*去掉，剩下的就是指针指向某个变量的类型。也就是说p将来指向的是一个int类型的变量（不考虑强制类型转换）

那么再回过头来看

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

，把指针名

compar

和

*

去了，剩下的是

int (const void*, const void*))

这是一个函数。按照上面的理解，该指针在将来是指向一个函数的，那么现在应该能理解指针为啥指向函数了吧

综上所述，参数④是一个函数指针，该指针指向了一个函数，该函数的形参为

(const void*, const void*)

，该函数的返回类型为

int

。

接着分析，既然知道了参数④是一个函数指针，是指针，那么传参的时候肯定是需要传地址，传谁的地址？传函数的地址！

换句话说，如果我们想要使用qsort函数，那么我们需要一个形参一致，返回类型一致的函数，这个函数是需要使用qsort的人自己去实现的。因为只有使用qsort的人才知道自己想要比较什么，比较元素的类型又是什么。

那这个函数的返回值又有什么含义呢。
比较的两个元素分别e1,e2。
如果e1大于e2，返回一个大于0的数
如果e1小于e2，返回一个小于0的数
如果e1等于e2，返回0

那使用qsort的人去实现的这个函数作用是什么？是比较方法，不同的类型比较的方式是不同的！如果是数与数之间的比较，做差即可。如果是字符之间的比较呢？做差就不适合了，需要使用

strcmp

。

讲了这么多，相信你应该有所了解，或许还不太理解，也没关系，通过下面的实例来理解上面我所说的！

🎃qsort应用实例

主函数

#include<stdio.h>#include<stdlib.h>#include<string.h>struct S   //定义一个结构体类型{char name[10];int age;};intmain(){test1();test2();return0;}

🌳比较整形/浮点型

数与数之间的比较做差即可。
返回值也就是这个差值。
写的时候注意要强制类型转换，转换成什么类型的指针取决于你想要比较的元素类型，比较的是int类型就int，比较的是float类型就float

intint_cmp(constvoid* e1,constvoid* e2){return*(int*)e1 -*(int*)e2;//e1-e2排的是升序//降序的话，需要将e1,e2换个位置}voidtest1(){int arr[10]={5,2,1,3,4,6,9,8,7,10};int sz =sizeof(arr)/sizeof(arr[0]);qsort(arr, sz,sizeof(arr[0]), int_cmp);//arr是数组的地址，sz是数组元素的个数//sizeof(arr[0])，元素所占空间的大小//int_cmp，是函数的地址，该函数是使用qsort的人去实现int i =0;for(i =0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");}

🌴比较结构体的整形

在对结构体排序的时候，需要注意的是 ()

(struct S*)e1->age

这样写是不行的，需要将

(struct S*)e1

当作一个整体去使用，需要加上 ()
写成

((struct S*)e1)->age

intage_cmp(constvoid* e1,constvoid* e2){return((struct S*)e1)->age -((struct S*)e2)->age;}voidtest2(){struct S s[]={{"Zhang",40},{"Wang",20},{"Lisi",60}};//对结构体初始化int sz =sizeof(s)/sizeof(s[0]);//求数组的元素个数qsort(s, sz,sizeof(s[0]), age_cmp);//sizeof(s[0])，一个元素的大小//age_cmp，函数的地址。int i =0;for(i =0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}}

🌵比较结构体的字符串

对一些字符串函数不了解的点这

这里还是要强调一下，注意 ()
strcmp()本身也是有个括号的。
strcmp的返回值：大于返回一个大于0的数，小于返回小于0的数，等于返回0。
写的时候可以先从里面的写起
先把

(struct S*)e1)->name, ((struct S*)e2)->name

写出来，然后在复制粘贴到

strcmp()

的()里。

intname_cmp(constvoid* e1,constvoid* e2){returnstrcmp(((struct S*)e1)->name,((struct S*)e2)->name);}voidtest2(){struct S s[]={{"Zhang",40},{"Wang",20},{"Lisi",60}};int sz =sizeof(s)/sizeof(s[0]);qsort(s, sz,sizeof(s[0]), name_cmp);int i =0;for(i =0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}}

💡想成为一名优秀的程序猿，需要加点难度---- 模拟实现

🎈冒泡排序模拟实现

冒泡排序比较简单，这里就不再赘述如何来的了。
通过与普通版本的冒泡排序，对比去实现qsort的功能

✏普通版本的冒泡排序

voidBubble_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;}}}}

模拟实现的函数可以对着qsort的去写
这个比较容易

void Bubble_sort2(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

📄重点来了

冒泡排序中最主要的两个步骤是 比较 + 交换。

if(arr[j]> arr[j +1])//比较{//交换int tmp = arr[j];
            arr[j]= arr[j +1];            
            arr[j +1]= tmp;}

🎉先对比较进行转换

友情提示，需要对指针类型的意义要有所了解才能理解
不了解的点击"我"

base

的类型是

void*

上面有铺垫过，

void*

不可直接使用，需要通过强制类型转换。那转换成什么呢？转换成

int*

合适吗？

显然不合适，这样写，那我们如何实现比较任意类型的呢？

回归本源，内存的基本单位是字节，不管是哪种类型的元素，元素所占空间的大小肯定是可以确定的。

那我们可以这样：以字节为单位去偏移，虽然每一次偏移的步长只有1个字节，但只要我们知道了，一个元素所占空间的大小有n个字节。

那从当前位置向后偏移n次，不就是n个字节嘛？不就能够在内存中取到一个元素的吗？

这样一理，

base

需要强制类型转换为

char*

，那类型的大小如何得知呢？不正是我们的参数③–>size_t size吗

或许你还没理解，用图带你理解一下。

那现在还有一个问题那如何取到每一个元素呢？

数组与指针访问是互通的(操作符之间可以互用)，不了解点"我"

原先的是这样写的

if (arr[j] > arr[j + 1])

(指针类型是

int*

)我们是不是可以借鉴一下呢？

arr[j]

等价于

*(arr+j)

arr+j

的含义是以

arr

为起始地址

+j

向后偏移

j*4

个字节和我们写的

(char*)base+size

（含义是以

base

为起始地址向后偏移

size

个字节）
相比，不就少了什么不就少了

j*

吗，那我们这样写

(char*)base+size*j

和上面

arr+j

所表达的意思不就一样了吗？

还有一种理解，我们已经知道

(char*)base+size

表示的是第一个元素（是以base为起始地址的第一个元素）那第二个元素不就是

(char*)base+size + (char*)base+size

，第三个元素是

(char*)base+size + (char*)base+size + (char*)base+size

，那第j个元素不就是

(char*)base+size * j

吗？

怎么理解方便就怎么选择。

元素每一个元素能够取出来了，那该如何比较呢？

轮到我们所写的比较函数出场了。比较方法的函数已经有了，我们只需要传参即可。这样调用的函数又被称为回调函数

哪种调用呢？ 以指针的形式去调用函数，这个函数就被称为回调函数

这里的指针可以不用解引用，直接当作函数来使用。
为什么可以这样呢？还记得上面有说过，函数名就表示函数的地址， 这个地址不就是指针吗？那这个指针不就是函数名吗？函数调用是函数名(参数),这样一换不就是 指针(参数) 吗

🎐该决解的问题已经解决，那开始实现----比较

if(cmp((char*)base + j * width,(char*)base +(j +1)* width))

我这样写对吗？答案是不对，还少了点东西。我们这个函数返回值是一个整数，并不是 大于，小于，等于！ 要加上判断

if(cmp((char*)base + j * width,(char*)base +(j +1)* width)>0)

或许有人会有疑问，为什么在对比较函数中，传参只需要传地址，就可以比较两个元素的大小。

这是指针类型的作用，指针的类型决定了解引用(*)能够操作多大的空间。

比较函数是使用者实现的，对应的元素类型也是明确的，在接收地址后，根据强制类型转换后的类型，进行解引用操作，可以取到对应的元素内容，那也就能完成比较。

🎉最后一步交换的实现

交换步骤先来看原冒泡的实现

//交换int tmp = arr[j];
        arr[j]= arr[j +1];
        arr[j +1]= tmp;

按照上面已经有的经验，想要实现对任意类型元素的交换，我们仍然只能通过强制类型转换为

char*

以字节为单位去实现。

如果你曾经有模拟实现过strcpy的话，那现在这个问题对你来说很容易就能完成的。

没有模拟过的话，且听我分析。
交换是两个元素互换，交换实现的步骤是以字节为单位，一个字节一个字节的交换，循环的条件应该是很容易想到的，什么时候交换完成了呢？当一个元素中最后一个字节交换后就完成了一次交换。

这里有一堆的字符串函数等着你来模拟实现，其中有两个是挺有难度的噢，快点“我”~

整个想法有了，也可以开始实现了。如果我们把这一“动作”封装成函数是不是更显得"高大上"呢？也确实可以这样实现，而且也美观。
函数名为

Swap

形参和返回类型是什么呢？
返回类型容易考虑我们不需要返回类型。
那形参是啥？比较的是两个元素，这两个肯定需要传过去。
再加上我们是以字节为单位进行交换的，那结束的条件也需要传，结束条件就是我们元素的大小。
讲到这那已经可以开始实现了。

🩸问题解决开始实现----交换

//函数调用（交换两个元素，以及元素的大小）Swap((char*)base + j * width ,(char*)base +(j +1)* width ,width );//函数实现，选择哪种循环都行。voidSwap(char* e1,char* e2,int width){int i =0;for(i=0;i<width;i++){char tmp =*e2;*e2 =*e1;*e1 = tmp;
        e1++;
        e2++;}}

🛠冒泡排序模拟实现qsort完整代码

voidSwap(char* e1,char* e2,int width){int i =0;for(i =0; i < width; i++){char tmp =*e2;*e2 =*e1;*e1 = tmp;
        e1++;
        e2++;}}voidBubble_sort2(void* base,int sz,int width,int(*cmp)(constvoid* e1,constvoid* e2)){int i =0;for(i =0; i < sz -1; i++){int j =0;for(j =0; j < sz -1- i; j++){if(cmp((char*)base + j * width,(char*)base +(j +1)* width)>0){Swap((char*)base + j * width,(char*)base +(j +1)* width,width);}}}}

同样可以来测试一下

intint_cmp(constvoid* e1,constvoid* e2){return*(int*)e1 -*(int*)e2;}voidtest1(){int arr[]={2,5,3,1,9,6,4,8,7,10};int sz =sizeof(arr)/sizeof(arr[0]);Bubble_sort2(arr, sz,sizeof(arr[0]), int_cmp);print(arr, sz);}struct S
{char name[10];int age;};intstruct_name_cmp(constvoid* e1,constvoid* e2){returnstrcmp(((struct S*)e1)->name,((struct S*)e2)->name);}intstruct_age_cmp(constvoid* e1,constvoid* e2){return((struct S*)e1)->age -((struct S*)e2)->age;}voidtest2(){struct S s[]={{"Zhang",40},{"Li",20},{"Wang",50}};int sz =sizeof(s)/sizeof(s[0]);//Bubble_sort2(s, sz, sizeof(s[0]), struct_name_cmp);Bubble_sort2(s, sz,sizeof(s[0]), struct_age_cmp);int i =0;for(i =0; i < sz; i++){printf("%s  %d\n", s[i].name, s[i].age);}}intmain(){//test1();test2();return0;}

对结构体年龄排序

对结构体姓名排序

对数组排序

🎈插入排序实现qsort

🎠原版插入排序

voidInsert(int* arr,int sz){int i =1;for(i =1; i < sz; i++){int t = arr[i];//待插入的元素int j = i -1;while(j >=0&& t < arr[j]){//交换
            arr[j +1]= arr[j];
            j--;}
        arr[j +1]= t;}}intmain(){int arr[10]={5,2,3,8,9,4,7,1,10,6};int sz =sizeof(arr)/sizeof(arr[0]);int i =0;Insert(arr, sz);for(i =0; i <10; i++){printf("%d ", arr[i]);}return0;}

✨关键处分析

插入排序需要注意的是这两个表达式

int t = arr[i];

和

arr[j + 1] = t;

为了达到实现任意类型的排序，肯定不能这样写。

那我是这样处理的：

为了存储插入的元素，你需要空间，需要多大根据元素的类型的大小。
我首先想到的是用动态内存函数，通过

malloc

开辟空间来存储要插入的元素。地址的类型需要设置为

char*

另外如何实现赋值这一过程呢？
如果写过

strcpy

的模拟实现那应该也能够想到，我们可以通过

Copy

函数进行拷贝，就相对于完成了一次赋值。

一些函数的模拟实现写一遍，自己有更深的理解，很容易能想到，多去模拟实现这些函数也能提升自己代码能力。
点"我“，即可找到那些模拟的字符串函数

voidSwap(char* e1,char* e2,int width){int i =0;for(i =0; i < width; i++){char tmp =*e2;*e2 =*e1;*e1 = tmp;
        e1++;
        e2++;}}voidCopy(char* e1,constchar* e2,int width){while(width){*e1 =*e2;
        e1++;
        e2++;
        width--;}}voidInsert2(void* base,int num,int size,int(*cmp)(constvoid* e1,constvoid* e2)){int i =1;char* t =(char*)malloc(size);if(NULL==t)//检测开辟是否成功{perror("malloc");return;}for(i =1; i < num; i++){//拷贝赋值Copy(t,(char*)base + size * i, size);int j = i -1;//比较while(j >=0&&cmp(t,(char*)base + size * j)<0){//交换Swap((char*)base + size *(j +1),(char*)base + size * j, size);
        
            j--;}//拷贝赋值Copy((char*)base + size *(j +1), t, size);}//对堆区开辟的空间释放free(t);//指针置为空，避免野指针
    t=NULL}

测试

intstruct_name_cmp(constvoid* e1,constvoid* e2){returnstrcmp(((struct S*)e1)->name,((struct S*)e2)->name);}intstruct_age_cmp(constvoid* e1,constvoid* e2){return((struct S*)e1)->age -((struct S*)e2)->age;}intcmp_int(constvoid* e1,constvoid* e2){return*(int*)e1 -*(int*)e2;}voidtest2(){struct S s[]={{"Zhang",40},{"Li",20},{"Wang",50}};int sz =sizeof(s)/sizeof(s[0]);Insert2(s, sz,sizeof(s[0]), struct_name_cmp);Insert2(s, sz,sizeof(s[0]), struct_age_cmp);int i =0;for(i =0; i < sz; i++){printf("%s  %d\n", s[i].name, s[i].age);}}voidtest1(){int arr[10]={5,2,3,8,9,4,7,1,10,6};int sz =sizeof(arr)/sizeof(arr[0]);int i =0;Insert2(arr,sz,sizeof(int),cmp_int);for(i =0; i <10; i++){printf("%d ", arr[i]);}}intmain(){//test1();test2();return0;}

结束语

看完之后，还等什么呢，快点自己模拟实现一下属于你的qsort吧~