各位CSDN的uu们你们好呀，今天小雅兰的内容还是我们的深度剖析指针呀，上篇博客我们学习了回调函数这个知识点，但是没有写完，因为：小雅兰觉得qsort值得单独写出来！！！好啦，就让我们进入指针的世界吧
qsort是一个库函数，是用来排序的库函数，使用的是快速排序的方法
quicksort
我们先来复习一下之前所学习过的一种算法——冒泡排序
冒泡排序——“C”_认真学习的小雅兰.的博客-CSDN博客
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> void bubble_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; } } } } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } } int main() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; //排序 //使用冒泡排序的算法，来排序 int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz); //打印 print_arr(arr, sz); return 0; }
但是，这个算法最大的缺点就是只能排序整型，如果未来要排序浮点数呢？如果未来要排序一些字符串呢？结构体呢？那么，这个函数就搞不定了，仅仅能排序固定类型的数据
qsort的好处：
现成的
可以排序任意类型的数据
void qsort( void *base,//指向了待排序数组的第一个元素
size_t num,//待排序的元素个数
size_t width,//每个元素的大小，单位是字节
int (__cdecl *compare )(const void *elem1, const void *elem2 )
//函数指针
//指向一个函数，这个函数可以比较两个元素的大小
);
qsort是可以排序任意类型的数据的
比较两个整数的大小，> < =
比较两个字符串，strcmp
比较两个结构体数据（学生：张三、李四），指定比较的标准，拿什么比较？
int a=10;
void * p=&a;
//void * ——无具体类型的指针，所以它可以接收任何类型的地址
//*p;//err void*的指针不能使用解引用操作符
//p++;//err
下面，我们来使用一下qsort函数：
#include<stdio.h> #include<stdlib.h> //qsort函数的使用者提供这个函数 int cmp_int(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } test1() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[0]); //使用qsort来排序整型数组，这里就要提供一个比较函数，这个比较函数能够比较2个整数的大小 //qsort默认是排成升序的 qsort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr, sz); } int main() { test1(); return 0; }
qsort这个库函数是不是很神奇呢？下面还有更加神奇的！！！
我们来测试一下qsort排序结构体数据
#include<stdio.h> #include<stdlib.h> //qsort函数的使用者提供这个函数 int cmp_int(const void* p1, const void* p2) { return *(int*)p1 - *(int*)p2; } struct Stu { char name[20]; int age; }; int cmp_stu_by_age(const void* p1, const void* p2) { return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age; } void print(struct Stu* ps, int sz) { int i = 0; for (i = 0; i < 3; i++) { printf("%d\n", ps[i].age); } } void test2() { struct Stu s[] = { {"zhangsan",30},{"lisi",25 }, { "wangwu",50 } }; int sz = sizeof(s) / sizeof(s[0]); //测试按照年龄来排序 qsort(s, sz, sizeof(s[0]), cmp_stu_by_age); print(s, sz); } int main() { test2(); return 0; }
#include<stdio.h> #include<stdlib.h> #include<string.h> struct Stu { char name[20]; int age; }; int cmp_stu_by_name(const void* p1, const void* p2) { return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name); } void print(struct Stu *ps, int sz) { int i = 0; for (i = 0; i < 3; i++) { printf("%s\n", ps[i].name); } } void test2() { struct Stu s[] = { {"zhangsan",30},{"lisi",25},{"wangwu",50} }; int sz = sizeof(s) / sizeof(s[0]); //测试按照名字来排序 qsort(s, sz, sizeof(s[0]), cmp_stu_by_name); print(s, sz); } int main() { test2(); return 0; }
qsort底层是快速排序，但是小雅兰还没有学习快速排序的思想，所以暂时还不能之间实现qsort，所以使用冒泡排序的思想来实现一个类似于qsort这个功能的冒泡排序函数bubble_sort
使用回调函数，模拟实现qsort（采用冒泡的方式）。
测试函数：
void test3() { int arr[] = { 3,1,5,2,4,9,8,6,7,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr, sz); }
主函数：
int main() { test3(); return 0; }
模拟实现的bubble_sort()函数：
//假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2)) { //base 待排序数组的第一个元素 //元素个数和元素个数的大小不可能是负数，所以是size_t类型 //函数指针 //要确定趟数 size_t i = 0; for (i = 0; i < num - 1; i++) { //一趟冒泡排序的过程 size_t j = 0; int flag = 1;//假设已经有序了 //标记变量 for (j = 0; j < num - 1 - i ; j++) { //两个相邻的元素比较 //arr[j] arr[j+1] if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) { //强制类型转换为char* //因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组 flag = 0; //交换 Swap((char*)base + j * width, (char*)base + (j + 1) * width, width); } } if (flag == 1) { break; } } }
在bubble_sort()函数中，调用了自定义的函数Swap，是用来交换元素的：
int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void* { return *(int*)p1 - *(int*)p2; } 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 print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); }
完整代码如下所示：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void* { return *(int*)p1 - *(int*)p2; } 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++; } } //假设排序为升序 //希望这个bubble_sort函数可以排序任意类型的数据 void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2)) { //base 待排序数组的第一个元素 //元素个数和元素个数的大小不可能是负数，所以是size_t类型 //函数指针 //要确定趟数 size_t i = 0; for (i = 0; i < num - 1; i++) { //一趟冒泡排序的过程 size_t j = 0; int flag = 1;//假设已经有序了 //标记变量 for (j = 0; j < num - 1 - i ; j++) { //两个相邻的元素比较 //arr[j] arr[j+1] if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) { //强制类型转换为char* //因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组 flag = 0; //交换 Swap((char*)base + j * width, (char*)base + (j + 1) * width, width); } } if (flag == 1) { break; } } } void print_arr(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } void test3() { int arr[] = { 3,1,5,2,4,9,8,6,7,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr, sz); } int main() { test3(); return 0; }
好啦，小雅兰玩转的qsort就到这里啦，这篇博客难度很大，确实花了小雅兰很多时间，未来还要继续加油呀！！！
