【C语言】模拟实现库函数qsort

qsort的头文件是stdlib.h

他的四个参数分别是要进行排序的数组base的首地址，base数组的元素个数，每个元素的大小，以及一个函数指针，这个函数指针指向了一个函数，这个函数的参数是两个void*类型的指针，返回类型是int，要求这个函数能够比较参数（这个函数的参数是两个指针）指向的两个元素的大小，规定如果elem1指向的元素比elem2指向的元素大，那这个函数就返回一个大于零的数，反之就返回一个小于零的数，如果elem1和elem2指向的元素一样大，就返回0。

void*类型的指针可以接收任何类型的地址，但是不能直接解引用，由于我们不知道未来要比较的两个函数是什么类型的，那就只能写成void*类型，就可以接收任何类型了，在解引用之前强制类型转换即可。

qsort默认是以升序排列的（如果要降序排列，只需要比较大小的函数返回值上用相反的逻辑即可，比如elem1指向的元素如果比elem2大，就返回一个小于零的数），并且可以排列任何类型的数组。来看一个例子

下面我们将使用回调函数模拟实现qsort，由于目前没有学习快速排序，因此使用冒泡排序代替。

模拟实现，我们就把参数设置成和库函数qsort一样，最后一个函数指针指向的是一个能比较两个元素大小的函数，需要使用者自己编写。

我们排序使用的是冒泡排序的思想，就是比较相邻的两个元素，如果前面比后面大，就交换，那现在的问题是当时冒泡排序是针对整形数组的，比较就是直接base[j]和base[j+1]进行比较即可，但是现在我们想要这个my_sort类型能够对任意类型的数据进行排序，就不能简单的写成base[j]和base[j+1]，因为我们连base的类型都不知道，当然也不知道+1会跳过几个字节，也就不知道+1是不是拿到了和base[j]相邻的元素。那么我们干脆一个字节一个字节的操作，因为不管什么类型，大小至少也是一个字节，那如何操作一个字节？很简单，使用char类型的指针即可。因此不管base代表什么类型的数组，我们都先把base强制类型转换成char*类型，那么base[j]其实就是(char*)base+j*size，与他相邻的元素就是(char*)base+(j+1)*size。

这样我们就拿到了要比较的两个元素，但是这两个元素如何比较？直接使用大于号显然是不合理的，这时候就用到了我们的第四个参数，cmp函数，我们需要自己写一个能够比较两个元素大小的函数，并且规定如果前者大，就返回一个大于0的数，反之就返回一个小于0的数，如果二者相等，就返回0。

通过判断cmp函数的返回值，我们就知道了需不需要交换这两个元素。那问题又来了，如何交换？直接创建临时变量吗？那临时变量是什么类型的呢？但是要交换的数据是什么类型，他们最小也有一个字节，那么我们直接一个字节一个字节的交换就行，什么时候才算交换结束呢？当然是交换完size个字节后，就结束了。如图是swap函数的交换

这样我们的my_sort函数就可以正常使用了，比如我们要排序的是一个整形数组，我们就要去写一个能够比较两个整形数据的函数，比如这样写

如果我们要比较两个结构体类型的数据呢？

假如结构体类型是这样的

如何比较两个struct stu类型变量的大小？

由于上面的结构体类型含有两个成员变量，那么要比较struct sut类型变量的大小，就可以按照name的大小来进行比较，也可以按照age的大小进行比较，当然如果按照name的大小来进行比较，就不能直接相减了，因为字符串的比较是用库函数strcmp，这个库函数的返回值逻辑与我们的cmp函数一致，也是前者大就返回大于零的数，后者大就返回小于零的数，一样大就返回0，因此我们如果按照name的大小来比较的话，直接返回strcmp的值就可以，如图

注：由于空指针是无法进行解引用操作的，因此我们在写cmp函数的时候都需要进行强制类型转换，要比较的是什么类型的，就强制类型转换成对应的指针。