【数据结构】第十九弹---C语言实现冒泡排序算法
✨个人主页： 熬夜学编程的小林
💗系列专栏： 【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)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
for (int i = 0; i a[j + 1])//前面的值大于后面的值则交换
{
Swap(&a[j], &a[j + 1]);
}
}
}
}
3、代码的优化
如果一次遍历，没有数据进行交换，则证明数组已经排好了顺序，不需要继续遍历，则引入exchange变量标志记录第一次遍历是否有数据交换。
void BubbleSort(int* a, int n)
{
for (int i = 0; i a[j + 1])//相邻两个数进行比较
{
Swap(&a[j], &a[j + 1]);//前面的值大于后面的值则交换
exchange = true;
}
}
if (exchange == false)//值没变则退出内循环
break;
}
}
4、代码的测试
测试代码：
//测试冒泡排序
int main()
{
int a[] = { 9,8,7,6,5,4,3,2,1,0 };//给一组数据
int sz = sizeof(a) / sizeof(a[0]);//计算数组元素个数
printf("排序前：\n");
ArrayPrint(a, sz);
BubbleSort(a, sz);
printf("排序后：\n");
ArrayPrint(a, sz);
return 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 num, //待排序数组元素个数
size_t size,//待排序数组元素类型大小，单位为字节
int (*com)(const void*,const void*)//函数指针 如何进行比较函数
);
6.2、交换数据函数
void swap(char* buf1, char* buf2, size_t size);
思想：
以1个字节为单位对两个指针指向的内容进行交换，交换size次即可。
参数：
buf1：被交换的数据的地址。
buf2：被交换的数据的地址。
size：被交换数据类型的字节大小。
void swap(char* buf1, char* buf2, size_t size)
{
assert(buf1 && buf2);//断言，指针不为空才能交换
size_t i = 0;
for (i = 0; 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类型数据比较（升序）
int cmp(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
//int类型数据比较（降序）
int cmp(const void* e1, const void* e2)
{
return *(int*)e2 - *(int*)e1; //降序就是把e1，e2的位置交换一下
}
//字符串比较（按字母升序）
#include
int cmp(const void* e1, const void* e2)
{
return strcmp((char*)e1, (char*)e2); //字符串比较函数，与前面的比较规则一致
}
冒泡排序法的实现：
#include //引入头文件，使用assert函数断言
//交换数据
void swap(char* buf1, char* buf2, size_t size)
{
assert(buf1 && buf2);//断言，指针不为空才能交换
size_t i = 0;
for (i = 0; i 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);
}
void test1()
{
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.结构体演示
struct Stu
{
char name[20];
int age;
};
int cmp_stu_by_age(const void* e1,const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
void test2()
{
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);
}
测试结果：
总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
