1.什么是qsort函数
我们以前学习过的一些排序算法，如冒泡、希尔、快排等等，它们速度有快有满，但是这些排序都只能排序一种类型的变量，如果想排序另一种变量就需要另写一个排序， 那么有没有什么排序是“万能的”呢，什么类型数据都能排的呢？
答案就是qsort函数
qsort函数实现了一种快速排序算法，对一个由n个元素组成的数组进行排序，每个元素的宽度为字节。参数base是一个指向要排序的数组基数的指针，qsort用排序后的元素覆盖这个数组。参数compare是一个指向用户提供的例程的指针，用于比较两个数组元素并返回一个指定它们之间关系的值。
这是qsort函数的官方定义：
这个函数有四个参数
第一个参数base是待排数组的起始地址
第二个参数num是数组的元素个数，也就是数组的大小
第三个参数width是一个元素的大小，单位是字节，也就是一个元素所占大小
第四个参数compare是一个函数指针，这个参数较为复杂，接下来我们展开讲
在排序中，比较整形或比较浮点型可以用大于，小于，等于；比较两个字符串可以用strcmp函数；但是如果比较两个结构体怎么比较，按照结构体中哪个元素进行比较呢？所以不同类型的元素应用不同的方法去比较
这也就是compare这个函数干的事，在这个函数里，我们自己写两个元素应该怎么比较
将compare这个函数指针传回qsort函数，qsort就会按照compare函数中比较的方法，对数组中元素进行比较
在compare函数中，elem1指的是要比较的两个元素中第一个元素的地址，elem2是另一个要比较的元素的地址，因为这个函数官方在定义的时候，并不知道要比较什么类型的元素，所以用void*类型.
compare函数是有返回值的：
elem1小于elem2，返回负数
elem1大于elem2，返回正数
elem1等于elem2，返回0
按照comparer函数的定义，数组以递增的顺序进行排序。要按递减顺序对数组进行排序，颠倒comparer函数中 "大于 "和 "小于 "的含义。
2.实现一个qsort函数
有一个存放int类型变量的数组arr
int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; 1
然后使用qsort函数
第一个参数是数组名arr
第二个参数是数组长度int size = sizeof(arr) / sizeof(arr[0]);
第三个参数是一个元素的大小sizeof(arr[0])
第四个参数是函数指针cmp_int
在cmp_int函数中，因为传的参数是void*类型，并且待排数组是int类型的，所以在比较函数中，需要将void*类型的变量强制转换成int*类型的指针再进行解引用
如果是排升序，就按照cmp_int函数中参数的顺序将两个指针解引用后相减，否则就颠倒两个指针的顺序
代码如下：
#include <stdio.h> int cmp_int(const void* e1, const void* e2) { //排升序 return *(int*)e1 - *(int*)e2; //排降序 //return *(int*)e2 - *(int*)e1; } int main() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; int size = sizeof(arr) / sizeof(arr[0]); qsort(arr, size, sizeof(arr[0]), cmp_int); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } }
3.用qsort函数排序一个结构体
下面我们用qsort排序一个结构体
结构体如下：
struct stu { int age; char name[10]; };
然后使用qsort函数，结构体中有整形和字符串两个元素，这两个元素都可以进行比较和排序
首先我们按照年龄来排序，比较年龄的函数命名为cmp_by_age，将两个void*类型的形参强转成struct stu*类型，访问它们的age元素并相减
int cmp_by_age(const void* e1, const void* e2) { return ((struct stu*)e1)->age - ((struct stu*)e2)->age; }
首先我们按照姓名来排序，比较年龄的函数命名为cmp_by_name，将两个void*类型的形参强转成struct stu*类型，访问它们的name元素,可以用strcmp比较字符串间的大小
int cmp_by_name(const void* e1, const void* e2) { return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); }
完整代码：
#include <stdio.h> #include <string.h> struct stu { int age; char name[10]; }; int cmp_by_age(const void* e1, const void* e2) { return ((struct stu*)e1)->age - ((struct stu*)e2)->age; } int cmp_by_name(const void* e1, const void* e2) { return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); } int main() { struct stu arr[3] = { {18,"jack"},{30,"andy"},{25,"ride"} }; int size = sizeof(arr) / sizeof(arr[0]); qsort(arr, size, sizeof(arr[0]), cmp_by_age); //按照年龄排序 qsort(arr, size, sizeof(arr[0]), cmp_by_name); //按照姓名排序 return 0; }
4.模仿qsort的功能实现一个通用的冒泡排序
模仿qsort函数实现冒泡排序，改进后的冒泡排序的函数列表中应与qsort函数一样
void BubbleSort(void* base, size_t size,size_t width,int(*cmp)(const void* e1,const void*e2))
1
在以往的冒泡排序中，有两层循环，在两层循环中有一个比较两个数大小的if语句，在if语句中有一个交换语句
在改进型的冒泡中，也都是这些语句，只不过改进的是if语句中判断两个数大小和交换函数而已
在改进的冒泡排序中，比较两个元素的大小是调用额外定义出的cmp函数
但是怎么将两个待比较的元素传到cmp函数中是个问题，因为接收进来的数组是void*类型的，不知道元素具体是什么类型，无法用下标去访问所以只能将base强转成char*类型，通过指针的偏移量去访问每个元素，每两个元素中间隔着一个width字节的宽度，所以用(char*)base+j*width取出第一个元素的地址，用(char*)base+(j+1)*width取出第二个元素的地址
放到cmp函数中进行比较
cmp((char*)base + j * width, (char*)base + (j + 1) * width)
1
紧接着如果两个元素需要进行交换，就要使用交换函数，还是因为不知到元素是什么类型的，所以还是一个字节一个字节得交换
void swap(char* buf1, char* buf2, int width) { for (int i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } }
2
此时，模仿qsort函数实现冒泡排序就完成了，下面是完整代码：
#include<stdio.h> #include <string.h> struct stu { int age; char name[10]; }; int cmp_by_age(const void* e1, const void* e2) { return ((struct stu*)e1)->age - ((struct stu*)e2)->age; } int cmp_by_name(const void* e1, const void* e2) { return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); } int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } void swap(char* buf1, char* buf2, int width) { for (int i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void BubbleSort(void* base, size_t size,size_t width,int(*cmp)(const void* e1,const void*e2)) { int i = 0; for (i = 0; i < size-1; i++) { int j = 0; for (j = 0; j < size - i - 1; j++) { if (cmp((char*)base + j * width, (char*)base + (j + 1) * width)>0) { swap((char*)base + j * width, (char*)base + (j + 1) * width, width); } } } } void test1() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; int size = sizeof(arr) / sizeof(arr[0]); BubbleSort(arr, size, sizeof(arr[0]), cmp_int); } void test2() { struct stu arr[3] = { {18,"jack"},{40,"andy"},{35,"mary"} }; int size = sizeof(arr) / sizeof(arr[0]); BubbleSort(arr, size, sizeof(arr[0]), cmp_by_age);//按照年龄排序 BubbleSort(arr, size, sizeof(arr[0]), cmp_by_name);//按照姓名排序 } int main() { test1(); test2(); }
