✨个人主页： 熬夜学编程的小林
💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】
目录
1、冒泡排序基本思想
2、代码的初步实现
3、代码的优化
4、代码的测试
5、时空复杂度分析
6、模拟实现qsort
6.1、冒泡排序函数
6.2、交换数据函数
6.3、比较函数
总结
1、冒泡排序基本思想
冒泡排序法：（Bubble sort）是一种基础的交换排序。对数组进行遍历，每次对相邻两个进行比较大小，若大的数值在前面则交换位置（升序），完成一趟遍历后数组中最大的数值到了数组的末尾位置，再对前面n-1个数值进行相同的遍历，完成n-1次遍历则排序完成。
1. 第一趟对0~n-1遍历，依次对比前后的大小，若是不满足前小后大就交换，此时最大的数就被挪到了最后一个位置。
2. 对0~n-2遍历，继续比较前后大小，此时前n-2个数中最大的数就到了倒数第二个位置。
3. 重复上述动作继续遍历，每一次都将最大的数向后挤，直到遍历完毕排序成功。
2、代码的初步实现
对int 类型的数进行升序排序。
void Swap(int* p1, int* p2)
void BubbleSort(int* a, int n)
for (int i = 0; i < n - 1; i++)//遍历n-1次
for (int j = 0; j < n - 1 - i; j++)//相邻两个数进行比较
if (a[j] > a[j + 1])//前面的值大于后面的值则交换
如果一次遍历，没有数据进行交换，则证明数组已经排好了顺序，不需要继续遍历，则引入exchange变量标志记录第一次遍历是否有数据交换。
void BubbleSort(int* a, int n)
for (int i = 0; i < n - 1; i++)
bool exchange = false;//默认false，值没变则没有交换
for (int j = 0; j < n - 1 - i; j++)//遍历n-1次
if (a[j] > a[j + 1])//相邻两个数进行比较
Swap(&a[j], &a[j + 1]);//前面的值大于后面的值则交换
if (exchange == false)//值没变则退出内循环
测试代码：
int a[]
= {
9,8,7,6,5,4,3,2,1,0 };
//给一组
数据
int sz = sizeof(a) / sizeof(a[0]);//计算数组元素个数
测试结果：
5、时空复杂度分析
时间复杂度：
最坏情况：
当我们需要排升序的时候，原数组为降序，则为最坏情况。此时每次交换操作需要比较的次数从 n-1 次减少到 1 次，总共的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2，这是一个二次函数，因此时间复杂度为 O(n^2)。
最好情况：
当我们需要排升序时，原数组也是升序，我们只需要循环n次则可以判断结束，此时时间复杂度为O(N)。
由于时间复杂度取决于最坏情况，因此冒泡排序的时间复杂度为O(N^2)。
空间复杂度：
冒泡排序是一种原地排序算法，除了输入数组外，它只需要有限的几个变量（比如，交换标记和循环计数器）。因此，它的空间复杂度为常数空间O(1)。
6、模拟实现qsort
C语言中库函数 qsort是通过函数指针cmp传入数据类型的比较方式，实现对各种数据类型都能进行排序的功能。
我们将模仿qsort函数使用冒泡排序算法实现对各种数据类型都能进行排序的函数，并且使用const关键字严格限制参的属性，达到很高的健壮性要求。
6.1、冒泡排序函数
库函数qsort()函数接口：
void qsort (void* base, size_t num, size_t size,
int (*com)(const void*,const void*));
模拟实现的函数接口：
void bubble_
sort(void
* base,
//待排序数组首元素
地址
size_t size,//待排序数组元素类型大小，单位为字节
int (*com)(const void*,const void*)//函数指针 如何进行比较函数
6.2、交换数据函数
void swap(char
* buf
1, char
* buf
2,
size_t
size);
思想：
以1个字节为单位对两个指针指向的内容进行交换，交换size次即可。
参数：
buf1：被交换的数据的地址。buf2：被交换的数据的地址。size：被交换数据类型的字节大小。
void swap(char* buf1, char* buf2, size_t size)
assert(buf1 && buf2);//断言，指针不为空才能交换
for (i = 0; i < size; i++)
6.3、比较函数
int cmp(const void* e1, const void* e2);
void*是一个空类型的指针，可以存放任意类型的指针。
此处就用到了void*,void*为空指针，不能直接使用，但是可以强转为其他的任何类型，那么此处我们应该强转成什么类型呢？直接强转成int*？很显然，如果强转为int*，那么char*,short*就不好进行转化了，因此此处转化为char*，如果要用到其他的类型，我们通过+数据类型大小就可以得到。因此我们需要将指针转换成char*，依次按照字节进行交换。
返回值：
大于0，e1大；等于0，一样大；小于0，e2大。
参数：
e1：被比较的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容。e1：被比较的数据的地址，由void*指针接收，由const限制不能改变指针指向，但可以改变指针指向的内容。
函数体：
由用户自定义实现数值的比较规则。
传参：
1. 被比较数值的地址由void*指针接收。
2. 数值在数组中第 i 个位置：将void*转换成char指针，(char*)base + i*size 。
一些规则的演示:
int cmp(const void* e1, const void* e2)
return *(int*)e1 - *(int*)e2;
int cmp(const void* e1, const void* e2)
return *(int
*)e
2 - *(int
*)e
1;
//降序就是把e
1，e
2的
位置交换一下
int cmp(const void* e1, const void* e2)
return strcmp((char
*)e
1, (char
*)e
2);
//字符串比较函数，与前面的比较
规则一致
冒泡排序法的实现：
#include
<assert.h
> //引入头
文件<assert.h
>，使用assert函数断言
void swap(char* buf1, char* buf2, size_t size)
assert(buf1 && buf2);//断言，指针不为空才能交换
for (i = 0; i < size; i++)
void bubble_sort(void* base,size_t num,size_t size,int (*cmp)(const void* e1,const void* e2))
for (i = 0; i < num - 1; i++)
for (j = 0; j < num - 1 - i; j++)
//if (arr[j] > arr[j + 1])
//(char*)base+j*size,(char*)base+(j+1)*size
if(cmp((char*)base + j * size, (char*)base + (j + 1) * size)>0)
swap((char*)base + j * size, (char*)base + (j + 1) * size,size);
1.整型数组降序排序的演示：
int cmp_int(void* e1, void* e2)
return *((int*)e2) - *((int*)e1);
int arr[] = { 0,1,2,3,4,5,6,7,8,9 };
int sz = sizeof(arr) / sizeof(arr[0]);
print_arr(arr, sz);//打印数组元素
bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
print_arr(arr, sz);//打印数组元素
测试结果：
2.结构体演示
int cmp_stu_by_age(const void* e1,const void* e2)
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
struct Stu arr[] = { {"zhangsan",18},{"lisi",32},{"wangwu",20} };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
测试结果：
总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
