大家好，我是苏貝，本篇博客带大家了解如何用冒泡排序实现my_qsort，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️
一. 前言
用冒泡排序实现my_qsort？你或许觉得没有必要这样做，有现成的qsort函数，为什么还要自己写一个呢？于我而言，它可以让我对冒泡排序和qsort函数的印象加深。至于这到底有没有用，仁者见仁，智者见智吧。好了，就说这么多，现在让我们来回忆一下什么是冒泡排序和qsort函数。了解qsort函数
二. 冒泡排序
冒泡排序的原理：从左往右，依次比较相邻元素的大小，若符合条件，则两元素位置交换，每一趟可以找出最大值或最小值，并显示在序列的最右边。注意：冒泡排序只能排序整形序列，而qsort函数可以排序任意类型的序列
以想要升序排序为例，数组{5，2，4，3}，条件：如果相邻元素的左边>右边，则两元素位置交换。第一趟：5>2，交换位置。5>4，交换位置。5>3，交换位置。所以第一趟结束后数组为{2，4，3，5}。第二趟：2<4，不符合条件，位置不变。4>3，交换位置。所以第二趟结束后数组为{2，3，4，5}。第三趟，2<3，位置不变
代码：
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;
}
}
}
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
结果为：
三. 4个参数
3.1 第一个参数void* base
回顾上面的bubble_sort函数，它的第一个参数是int arr[ ],也可以写成int* arr,意思是接受一个整形数组的首元素地址。可是我们想要的是能接受任意类型的指针，所以用int* 就不合适，采用void* (void* 能接受任意类型的指针) ，所以第一个参数写为void* base
3.2 第二个参数szie_t num
上面的bubble_sort函数的第二个参数是int sz，代表数组有多少个元素，其实用int sz也可以，只是如果我们想更贴近qsort函数的话，将int改成size_t(无符号整型)也没有问题，写成szie_t num
3.3 第三个参数szie_t size
上面的bubble_sort函数并没有第三个参数，但是qsort函数有，意思是数组中的一个元素占多少个字节。因为我们不知道要排序的数组是什么类型的，所以如果没有第三个参数，我们无法表示出除首元素以外的地址，也就无法交换相邻元素
3.4 第四个参数int ( * cmp)(const void* e1,const void* e2)
第四个参数是用来判断相邻元素的关系，不能直接使用>,<,=的原因是如果我们想排序多个字符串，那么我们是不能使用>,<,=的，我们需要使用strcmp函数。不同类型的数组排序的函数可能不一样，像qsort函数一样，程序员又不知道用户想要排序的是什么类型的数组，所以程序员只能用函数指针cmp来接收用户自己写的cmp函数，而用户当然知道自己想要排序的数组的类型，所以用户能写出判断相邻元素的关系的函数
cmp函数的细节：
1.e1和e2是相邻元素的地址，被const修饰，保护e1和e2不能被修改
2.因为不知道排序的数组是什么类型的，所以e1和e2都是void * 类型的
3.如果相邻元素的左边>右边，返回>0的数；左边==右边，返回0；左边<右边，返回<0的数。所以返回值的类型为int
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* e1,const void* e2))
{}
四. bubble_sort函数
虽然函数的参数变化了很多，但函数原理并没有改变，依旧是比较相邻元素的大小，若符合条件，则两元素位置交换，每一趟可以找出最大值或最小值，并显示在序列的最右边。所以下面的框架不变（只将之前的sz变成了num），变得只是第二个for循环里面的内容，而里面的内容就是判断相邻元素的左边是否大于右边（以想要升序排序为例），如果是则交换位置，否则位置不变
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* e1,const void* e2))
{
int i = 0;
//排几趟
for (i = 0; i < num - 1; i++)
{
int j = 0;
//一趟排几次
for (j = 0; j < num - 1 - i; j++)
{
}
}
}
好的，那我们现在就想办法如何填写里面的代码，先是判断相邻元素的大小，用cmp函数，函数的两个参数分别为相邻元素的地址。那它们的地址该如何表示呢？首元素地址就是base，不用多说，那第二个元素呢？base+1？不行，我们不知道base的具体类型，所以base+1不知道会跳过几个字节。
那不妨将base强制类型转化为char* ，这样第二个元素（下标为1）的地址为（char*）base+1* size，第三个元素（下标为2）的地址为（char*）base+2* size，所以下标为j的地址为（char*）base+ j * size，代码为：
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{}
好的，那我们继续完善if语句后面的代码，代码的目的是将两元素交换位置，编写swap函数实现交换功能，swap函数的第一、二个参数自然是相邻元素的地址，即(char*)base + j * size, (char*)base + (j + 1) * size，它们都是char * 类型的，所以用两个char * 类型的指针来接收。
但问题又来了，我们平时实现a与b交换，是通过一个变量c来进行的，如下：
int a = 10;
int b = 20;
int c = a;
a = b;
b = c;
上面能交换的原因是我们知道了a和b的类型都是int，所以再创造一个int类型的变量作它们的中转站，即可实现交换。但我们事先并不知道数组的类型，所以不能创建一个和数组同类型的变量实现交换。那不如将两元素的每一个字节都交换（如下图），刚好它们是用char * 指针buf1、buf2来接收的，buf1++，buf2++即可访问两元素的每一个字节，因此我们也需要数组元素的字节数size作为swap函数的第三个参数
所以if语句后面的代码为：
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
swap函数：
void swap(char* buf1, char* buf2, size_t size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
所以bubble_sort函数的全部代码为：
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* e1,const void* e2))
{
int i = 0;
//排几趟
for (i = 0; i < num - 1; i++)
{
int j = 0;
//一趟排几次
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
五. 排序
对任意类型的数组排序都需要下面的代码，故把这些代码单独放在最前面，其余的main函数和cmp函数都因数组类型的变化而有所改变，所以将main函数和cmp函数单独写出来
void swap(char* buf1, char* buf2, size_t size)
{
int i = 0;
for (i = 0; i < size; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const void* e1,const void* e2))
{
int i = 0;
//排几趟
for (i = 0; i < num - 1; i++)
{
int j = 0;
//一趟排几次
for (j = 0; j < num - 1 - i; j++)
{
if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) > 0)
{
swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
}
}
}
}
5.1 对整型数组排序（char/short/int/long）
字符在内存中存储的是字符的ASCII码值，ASCII码是整型，所以char的写法同int
void cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;//升序
//return *(int*)e2 - *(int*)e1;//降序
}
int main()
{
int arr[] = { 9,8,7,6,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
//升序
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
//打印数组
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
5.2 对浮点型数组排序(float/double)
void cmp_double(const void* e1, const void* e2)
{
return *(double*)e1 > *(double*)e2 ? 1 : -1;//升序
//return *(double*)e1 < *(double*)e2 ? 1 : -1;
}
int main()
{
double arr[] = { 3.2 ,4.5, 2.4, 1.3 };
int sz = sizeof(arr) / sizeof(arr[0]);
//升序
bubble_sort(arr, sz, sizeof(arr[0]), cmp_double);
//打印数组
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%lf ", arr[i]);
}
printf("\n");
return 0;
}
5.3 对字符串长度排序
void cmp_string(const void* e1, const void* e2)
{
return strlen((char*)e1) - strlen((char*)e2);//升序
//return strlen((char*)e2) - strlen((char*)e1);//降序
}
int main()
{
char arr[][20] = { "helloworld","yes,sir","dian ge zan ba" };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr[0], sz, sizeof(arr[0]), cmp_string);
int i = 0;
for (i = 0; i < sz; i++)
printf("%s\n", arr[i]);
return 0;
}
5.4 对字符串大小排序
void cmp_string(const void* e1, const void* e2)
{
return strcmp((char*)e1, (char*)e2);//升序
//return strcmp((char*)e2， (char*)e1);//降序
}
int main()
{
char arr[][20] = { "helloworld","yes,sir","dian ge zan ba" };
int sz = sizeof(arr) / sizeof(arr[0]);
//升序
bubble_sort(arr, sz, sizeof(arr[0]), cmp_string);
//打印数组
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\n", arr[i]);
}
printf("\n");
return 0;
}
5.5 对结构体排序
struct Stu
{
char name[20];
int age;
};
void cmp_stu_by_age(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;//升序
//return ((struct Stu*)e2)->age - ((struct Stu*)e1)->age;//降序
}
int main()
{
struct Stu arr[] = { {"zhang",20},{"lisi",10},{"wangwu",30} };
int sz = sizeof(arr) / sizeof(arr[0]);
//升序
bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
//打印
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\t", arr[i].name);
printf("%d\n", arr[i].age);
}
printf("\n");
return 0;
}
文章来源：https://www.toymoban.com/news/detail-724576.html
好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️文章来源地址https://www.toymoban.com/news/detail-724576.html
到了这里，关于【C语言】用冒泡排序实现my_qsort的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
