✨个人主页: 熬夜学编程的小林
💗系列专栏: 【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 < n - 1; i++)//遍历n-1次{for (int j = 0; j < n - 1 - i; j++)//相邻两个数进行比较{if (a[j] > a[j + 1])//前面的值大于后面的值则交换{Swap(&a[j], &a[j + 1]);}}}
}
3、代码的优化
如果一次遍历,没有数据进行交换,则证明数组已经排好了顺序,不需要继续遍历,则引入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]);//前面的值大于后面的值则交换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 < size; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
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 <string.h>
int cmp(const void* e1, const void* e2)
{return strcmp((char*)e1, (char*)e2); //字符串比较函数,与前面的比较规则一致
}
冒泡排序法的实现:
#include <assert.h> //引入头文件<assert.h>,使用assert函数断言//交换数据
void swap(char* buf1, char* buf2, size_t size)
{assert(buf1 && buf2);//断言,指针不为空才能交换size_t 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))
{size_t i = 0;for (i = 0; i < num - 1; i++){size_t j = 0;for (j = 0; j < num - 1 - i; j++){//if (arr[j] > arr[j + 1])//(char*)base+j*size,(char*)base+(j+1)*sizeif(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);
}
测试结果:
总结
本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!