- 一、冒泡排序
- 二、qsort函数
- qsort函数的代码实现
- 三、回调函数概念：
- 四、使用回调函数，模拟实现qsort函数（采用冒泡的方式）
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。
回调函数不是由该函数的实现方直接调用，而是在特定的事件或者条件发送时由另外一方调用的，用于对该事件或条件进行响应。
是不是一脸懵？
没事，先把回调函数的定义放在一边，我们看一下冒泡排序吧
一、冒泡排序
还记得冒泡排序吗？
int main() {
int arr[] = { 1,3,5,7,9,2,4,6,8,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
//外层决定循环趟数
for (i = 0; i < sz - 1; i++) {
int j = 0;
//内层决定，本次循环的元素要对比的次数
for (j = 0; j < sz - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
for (i = 0; i < sz; i++) {
printf("%d ", arr[i]);
}
return 0;
}
冒泡排序是比较基础的排序方法。其中有个弊端就是，设计出来只能对一种同类型的数据排序。
有没有一种方法，能让我对 int 类型数据排序后，再去对 double 类型数据排序，甚至对结构体类型数据排序呢？
有，这就是要介绍的 qsort函数，它也算是回调函数的一种。
二、qsort函数
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*) );
它一共有四个参数，返回类型是 void。
解析：
void qsort ( void* base, --- base中存放的是待排序数据中第一个元素的地址，一般写数组名 size_t num, --- 排序数据元素的个数，也就是数组元素个数 size_t size, --- 排序数据中一个元素的大小，单位字节 int (*compar)(const void*,const void*) --- 用来比较待排序数据中的2个元素的函数 );
通俗来说：
我 qsort 函数什么类型都能排序，
但是你要把要排序的数组arr告诉我，数组元素有几个告诉我，数组的类型占几个字节告诉我，
还要你自己写一个比较这个数组的元素的方法给我。
这样我才能帮你办事（排序）。
…那我们写代码满足你的要求~
qsort函数的代码实现排序int类型数组
//记得引头文件 #include#include //数组元素比较函数 //因为是int类型数据，所以把e1和e2强转成int，就可以比较 //本身是指针类型，所以使用int*强转。 int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int main() { int arr[] = { 1,3,5,7,9,2,4,6,8,0 }; int sz = sizeof(arr) / sizeof(arr[0]); //数组名，数组长度，数组元素类型长度，数组元素比较函数 qsort(arr, sz, sizeof(int), cmp_int); //打印 for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
默认是升序排序？怎么让排序变成降序呢？
答案是改变下 数组元素比较函数。
int cmp_int(const void* e1, const void* e2) {
//把e1和e2的位置调换一下
return *(int*)e2 - *(int*)e1;
}
是不是感觉还好，不难
我们再试一下排序结构体类型数据~
#define _CRT_SECURE_NO_WARNINGS 1 #include#include struct Stu{ char name[20]; int age; }; //还是一样，强转成要排序的类型，进行比较 int sort_by_age(const void* e1, const void* e2) { return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; } int main() { struct Stu s[3] = { {"zhangsan",13},{"lisi",44},{"wanwu",35} }; int sz = sizeof(s) / sizeof(s[0]); //排序 qsort(s, sz, sizeof(s[0]), sort_by_age); //打印结构体 int i = 0; for (i = 0; i < sz; i++) { printf("%s ", s[i].name); printf("%dn", s[i].age); } return 0; }
修改成名字排序(引用strcmp函数来比较字符串)：
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include struct Stu{ char name[20]; int age; }; //还是一样，强转成要排序的类型，进行比较 int sort_by_age(const void* e1, const void* e2) { return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; } int sort_by_name(const void* e1, const void* e2) { return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name); } int main() { struct Stu s[3] = { {"zhangsan",13},{"lisi",44},{"wanwu",35} }; int sz = sizeof(s) / sizeof(s[0]); //排序 //qsort(s, sz, sizeof(s[0]), sort_by_age); qsort(s, sz, sizeof(s[0]), sort_by_name); //打印结构体 int i = 0; for (i = 0; i < sz; i++) { printf("%s ", s[i].name); printf("%dn", s[i].age); } return 0; }
小小总结一下：
qsort函数，
功能是可以排序任意类型的数组，
重点是要自定义数组元素比较函数，
比较的时候只需要把void类型强转成要排序的类型即可。
三、回调函数概念：
学了一圈，再回来看回调函数的定义。
回调函数就是一个通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。
我们把自定义函数（数组元素比较函数）的指针传递给 qsort 函数，当这个指针去调用数组元素比较函数，这就是回调函数。
回调函数不是由该函数的实现方直接调用，而是在特定的事件或者条件发送时由另外一方调用的，用于对该事件或条件进行响应。
我们的数组元素比较函数也不是该函数的实现方直接调用，而是在要排序特定类型数组的时候，由 qsort 函数调用。
简单来说：
数组元素比较函数的地址，作为参数传递给 qsort函数。
qsort 函数运行时，通过指针去调用数组元素比较函数，这种机制称为回调函数机制。
四、使用回调函数，模拟实现qsort函数（采用冒泡的方式）
好难的…
注释都改了几遍，希望能看得懂…
有四段代码，记得main方法进去，然后按照标注的1 2 3 4看。
#define _CRT_SECURE_NO_WARNINGS 1 #include//2.需要排序int类型，就把void*类型强转成int*，然后进行比较 int int_cmp(void* e1, void* e2) { //返回比较结果 return *((int*)e1) - *((int*)e2); } //4.两个数据交换，两个数据的类型是char* //int是4个字节，char是1个字节，在内存中4个连续的1字节的char，其实就是1个4字节的int //我们只需要把两个数据的4个连续的字节都交换了，就实现原本数据交换 //这么做也是为了通用性 void swap(char* buf1, char* buf2, int width) { int i = 0; //从第一个数据到第四个数据 for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } //3.实现bubble内部代码。 //base：可以接收任意类型的数据 //count，size：提供数组元素个数和元素类型宽度 //int(*cmp)(void*, void*)：函数指针，指向定义好的函数比较方法 void bubble(void* base, int count, int size, int(*cmp)(void*, void*)) { int i = 0; int j = 0; //采用的是冒泡排序的方式 for (i = 0; i < count - 1; i++) { for (j = 0; j < count - i - 1; j++) { //数组传递过来是void* base类型，强转成char*，加上size一个元素的宽度，就能够得到该元素 //这种方式是为了通用性， //char类型占用内存1字节，只要根据传递过来的元素size，就可以得到int、short、double等类型 //此代码功能性等同于arr[j]与arr[j+1]比较 if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { //有了两个数据，怎么交换？ //继续把数据强转成char*，和元素宽度size传递过去交换 swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } int main() { int arr[] = { 1,3,5,7,9,2,4,6,8,0 }; int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; //1.自定义回调函数bubble，完成数据排序 bubble(arr, sz, sizeof(int), int_cmp); //打印数据 for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("n"); return 0; }
排序结构体类型：按年龄排序
#define _CRT_SECURE_NO_WARNINGS 1 #includestruct Stu { char name[20]; int age; }; //2.把要排序的类型比较 int sort_by_age(void* e1, void* e2) { return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; } //4.两个数据交换，两个数据的类型是char //int是4个字节，char是1个字节， //在内存中4个连续的1字节的char，其实就是1个4字节的int //我们只需要把两个数据的4个连续的字节都交换了，就实现原本数据交换 //这么做也是为了通用性 void swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } //3.实现bubble内部代码。 //base：决定了可以任意类型数据排序 //count，size 提供数组元素个数和元素类型宽度 //int(*cmp)(void*, void*) 函数指针，指向定义好的函数比较方法 void bubble(void* base, int count, int size, int(*cmp)(void*, void*)) { int i = 0; int j = 0; //采用的是冒泡排序 for (i = 0; i < count - 1; i++) { for (j = 0; j < count - i - 1; j++) { //数组传递过来是void* base类型，强转成char*，加上size一个元素的宽度，就能够得到该元素 //这种方式是为了通用性， //char类型占用内存1字节，只要根据传递过来的元素size，就可以得到int、short、double等类型 //功能性等同于arr[j]与arr[j+1]比较 if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { //有了两个数据，怎么交换？ //继续把数据强转成char*，和元素宽度size传递过去交换 swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } int main() { struct Stu s[3] = { {"zhangsan",33},{"wangwu",55},{"lisi",44} }; int sz = sizeof(s) / sizeof(s[0]); int i = 0; //1.自定义回调函数，完成数据排序 bubble(s, sz, sizeof(struct Stu), sort_by_age); for (i = 0; i < sz; i++) { printf("%s ", s[i].name); printf("%dn", s[i].age); } printf("n"); return 0; }
排序结构体类型：按姓名排序
#define _CRT_SECURE_NO_WARNINGS 1 #include#include struct Stu { char name[20]; int age; }; int sort_by_name(void* e1, void* e2) { return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name); } void swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void bubble(void* base, int count, int size, int(*cmp)(void*, void*)) { int i = 0; int j = 0; //采用的是冒泡排序 for (i = 0; i < count - 1; i++) { for (j = 0; j < count - i - 1; j++) { if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } int main() { struct Stu s[3] = { {"zhangsan",33},{"wangwu",55},{"lisi",44} }; int sz = sizeof(s) / sizeof(s[0]); int i = 0; bubble(s, sz, sizeof(struct Stu), sort_by_name); for (i = 0; i < sz; i++) { printf("%s ", s[i].name); printf("%dn", s[i].age); } printf("n"); return 0; }
