前言
要模拟qsort()函数，我们首先要知道qsort()函数的特点：
- 使用快速排序的方法。
- 适用于任何数据类型的排序。
但由于部分学者还没有学习快速排序算法，所以本篇博客采用冒泡排序来模拟功能类似于qsort（）的函数bubble_sort。
C库对qsort()函数解释：
我们得到的关于qsort()函数参数信息：
void qsort(void* base, //指向排序的第一个元素 size_t num, //排序元素的个数 size_t size,//一个元素的大小，单位为字节 int (*cmp)(const void*, const void*)//函数指针类型 — 这个函数指针指向的函数，能够比较base指向数组的两个元素 );
1. 分析
我们首先来看一段普通的冒泡排序来排序整型数据
void bubblr_sort(int arr[], int sz) { //排序趟数 for (int i = 0; i < sz - 1; i++) { int tmp = 0; //每趟比较对数 for (int j = 0; j < sz - 1 - i; j++) { //假设升序，交换元素 if (arr[i] > arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; } } } } int main() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz); return 0; }
既然是用冒泡排序来模拟qsort()函数，我们可以以上面这段代码为基础，需改模拟实现。但存在几个问题！！
- 如何接受不同的数据类型，而不仅仅是整型。
- 对于不同的数据，比如结构体不能简单的用>或<还比较，那如何实现呢？
- 对于不同的数据类型，交换略有差异
2. 解决一，如何接受不同数据
void* 是C语言中的通用指针类型，可以指向任意类型的数据。所以我们可以将参数base定义为void*类型指针，来接受不同的数据。
void*用法拓展：
- 在使用void* 指针时，因为它不知道指向的类型的大小，需要将其转换为具体的指针类型才能进行操作。例如，可以将void 指针转换为int 指针，然后*对其进行赋值或者解引用操作。
2. void * 是一个无类型指针，在由于进行算术运算时，需要知道指针指向的具体数据类型的大小以便确定移动的字节数，所以它不能直接进行算术运算。
3. 解决二，如何实现不同数据的比较
由于不同的数据类型有不同的比较方法，我们可以在模拟的bubble_sort()函数参数中添加一个函数指针。将两个元素的比较方法，函数参数的形式进行传递。
Tips:
- 目前传入的数据以整型为例，所以我们定义比较函数名为cmp_int。在文章结尾将给出传入结构体数据的实现代码。
代码实现
//bubble_sort()实参传入 bubble_sort(arr,sz, sizeof(arr[0]), cmp_int); //bubble_sort()函数参数实现 void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) //cmp_int函数实现 int cmp_int(const void* p1, const void* p2) { //强制类型转换为int* ,在进行解引用 return (*(int*)p1 - *(int*)p2);//假设升序，则返回>0的数 //至于为什么返回这个数据，参考qsort()函数模仿即可 }
4. 解决三，如何实现不同数据交换
对于不同的数据，我们可以交换的两个数的起始地址强制类型转化为（char*）,然后计算出两个数据大小，最后两则一个一个字节交换即可。
代码实现
//数据交换我们封装一个Swap()函数 void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1] { char tmp = 0; while (size--) { tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } }
5. 模拟bubble_sort（）函数排序整型所有代码实现
由于是在冒泡排序的基础上来实现排序的，而排序的趟数和每趟排序的对数是不变的。所有我们只要解决上述问题，将相关代码进行替换即可。
代码实现
#include <stdio.h> int cmp_int(const void* p1, const void* p2) { return (*(int*)p1 - *(int*)p2); } void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1] { char tmp = 0; while (size--) { tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) { int i = 0; //趟数 for (i = 0; i < num; i++) { //一趟比较对数 //假设升序 for (int j = 0; j < num - 1 - i; j++) { if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)//比较两个元素，需要将arr[j]和arr[j+1]的地址传给cmp { //交换 Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } //测试bubble_sort排序整型数据 void test1() { int arr[] = { 4,2,5,8,3,8,34,23,1,54 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr,sz, sizeof(arr[0]), cmp_int); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } } int main() { test1(); return 0; }
运行结果：
6. 结构体排序实现
排序结构体时，Swap()和bubble_sort（）函数实现是相同的；我们只需要改变以下int_cmp函数即可（注：int_cmp()函数的名字依据比较数据不同，博主命名不同）
代码实现
#include <stdio.h> #include <string.h> void Swap(char* buf1, char* buf2, int size)//交换arr[i]和arr[i+1] { char tmp = 0; while (size--) { tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*)) { int i = 0; //趟数 for (i = 0; i < num; i++) { //一趟比较对数 //假设升序 for (int j = 0; j < num - 1 - i; j++) { //比较两个元素，需要将arr[j]和arr[j+1]的地址传给cmp if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { //交换 Swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } } //测试bubble_sort排序结构体数据 struct Stu { char name[20]; int age; }; int cmp_stu_by_name(const void* p1, const void* p2) { //比较两个字符时，需要借助函数strcmp()来实现 return strcmp(((struct Stu*)p1)->name ,((struct Stu*)p2)->name); } void test2() { struct Stu arr[] = { {"zahngsan",20},{"lisi",12},{"wangwu",43} }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name); } int main() { test2(); return 0; }
运行结果：
7. 结尾
本篇博客到此就结束了。如果对你有帮助，记得三连哦！感谢您的支持！！
