【数据结构】第十九弹---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 < 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);
}

测试结果: 

总结


本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/356429.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024信息系统、信号处理与通信技术国际会议(ICISPCT2024)

2024信息系统、信号处理与通信技术国际会议&#xff08;ICISPCT2024) 会议简介 2024国际信息系统、信号处理与通信技术大会&#xff08;ICISPCT2024&#xff09;将在青岛隆重开幕。本次会议旨在汇聚全球信息系统、信号处理和通信技术领域的专家学者&#xff0c;共同探索行业…

Docker之overlay2的迁移

原因 docker默认将文件及其容器放置在了系统盘的挂载区内&#xff0c;如果长期使用会发现系统挂载区被overlay2挤爆了,因此在一开始我们将其迁移在大容量外挂磁盘上,就可以避免系统盘被挤爆,放心使用. 具体操作 # 停止容器 systemctl stop docker# 修改容器配置&#xff0c…

基于STM32的智能病房监控和人脸识别系统设计(毕业设计)

摘 要 随着技术的不断进步和医疗需求的不断增长&#xff0c;智能病房控制系统有望在医疗领域发挥更大的作用。基于此&#xff0c;本文研究设计了一款低成本、操作简单、适用性强的基于STM32的智能病房监控和人脸识别系统。该系统通过STM32作为控制器和OpenMV对人脸分辨进行门…

常见调试器介绍

目录 常见调试器 1.1 ST-Link 1.2 DAPLink 1.3 JLink 常见调试器 市面上有很多的调试器&#xff0c;下面是大家比较常见的一些调试器&#xff0c; 比如&#xff1a;ST-Link、DAPLink、JLink、Ulink等 1.1 ST-Link ST-Link是一种用于STM8及STM32系列单片机的调试器和下载…

windows使用curl命令出现乱码的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

视频融合平台LntonCVS视频监控汇聚平台:构建多元接入与智能管理的安防新生态

一、视频融合平台概述 视频融合平台支持多种协议和设备类型的接入&#xff0c;包括GB28181、Onvif、RTSP、RTMP、海康SDK、Ehome、大华SDK、宇视SDK等。它能够统一整合和管理来自不同品牌、不同协议的视频资源&#xff0c;构建视频数据资源池&#xff0c;并通过视频资源目录为…

Mac安装多个jdk环境(jdk8+jdk17)保姆级

Mac安装多个jdk环境&#xff08;jdk8jdk17&#xff09;保姆级 背景&#xff1a;新机安装开发环境发现需要找很多文章&#xff0c;&#xff0c;&#xff0c;&#xff0c;这里一篇文章安装所有环境 文章目录 Mac安装多个jdk环境&#xff08;jdk8jdk17&#xff09;保姆级&#x1f…

从社交网络到元宇宙:Facebook的战略转型

随着科技的迅猛发展和数字化时代的深入&#xff0c;社交网络已不再局限于简单的信息交流和社交互动&#xff0c;而是逐步向更广阔、更深远的虚拟现实空间——元宇宙&#xff08;Metaverse&#xff09;转变。作为全球最大的社交网络平台之一&#xff0c;Facebook正在积极推动这一…

甘肃旅游服务平台的设计

甘肃旅游服务平台的设计 管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;公告信息管理&#xff0c;景点管理&#xff0c;酒店管理&#xff0c;基础数据管理&#xff0c;美食管理 前台账户功能包括&#xff1a;系统首页&#xf…

没等来百度惊艳的All in AI,却等来了国产之光的盘古大模型 5.0

6月21日&#xff0c;华为开发者大会&#xff08;HDC 2024&#xff09;在广东东莞正式开幕。盘古大模型5.0的更新&#xff0c;也是此次HDC2024的另一项重头戏。在过去的一年中&#xff0c;盘古大模型正在疯狂向各行各业渗透。 此次&#xff0c;华为方面展示了他们在具身智能、医…

squareline studio浅尝(1)在对话框添加键盘

因项目需要&#xff0c;需要修改IP地址等参数&#xff0c;需要编辑文本对话框内容&#xff0c;这时候就需要调用键盘&#xff0c;操作如下。主要为了做笔记。如有误导请及时留言。 1&#xff09;拖一个键盘到对话框页面。默认把它隐藏&#xff08;flag:hidden&#xff09; 2&…

MURF3040CTR-ASEMI智能AI应用MURF3040CTR

编辑&#xff1a;ll MURF3040CTR-ASEMI智能AI应用MURF3040CTR 型号&#xff1a;MURF3040CTR 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220F 恢复时间&#xff1a;35ns 最大平均正向电流&#xff08;IF&#xff09;&#xff1a;30A 最大循环峰值反向电压&#xff08;VR…

2024.6.23周报

目录 摘要 ABSTRACT 一、文献阅读 一、题目 二、摘要 三、网络架构 四、创新点 五、文章解读 1、Introduction 2、Method 3、实验 4、结论 二、代码实验 总结 摘要 本周阅读了一篇题目为NAS-PINN: NEURAL ARCHITECTURE SEARCH-GUIDED PHYSICS-INFORMED NEURAL N…

【面向就业的Linux基础】从入门到熟练,探索Linux的秘密(三)-shell语法

主要通过讲解shell中的一些基本语法&#xff0c;可以当作日常的笔记来进行查询和记忆。 文章目录 前言 一、shell 二、shell语法 1.运行方式 2.注释 3.变量 4.默认变量 5.数组 总结 前言 主要通过讲解shell中的一些基本语法&#xff0c;可以当作日常的笔记来进行查询和记忆。…

html--404页面

<!DOCTYPE html> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetUTF-8"> <meta http-equiv"X-UA-Compatible" content"IEedge,chrome1"> <title>404 错误页面不存在&…

某程序员:30岁了,老婆管钱,背着我买了50万股票,亏了20w,强制她清仓后又买了36万

“辛辛苦苦攒了几年钱&#xff0c;本想买房买车&#xff0c;结果全被老婆炒股亏掉了&#xff01;” 近日&#xff0c;一位30岁的程序员大哥在网上吐苦水&#xff0c;引发了网友们的热议。 这位程序员大哥和妻子结婚后&#xff0c;一直秉持着“男主外&#xff0c;女主内”的传统…

NLP大语言模型的缩放定律

一、简述 ​论文《神经语言模型的缩放定律》包含对交叉熵损失的语言模型性能的经验缩放定律的研究&#xff0c;重点关注Transformer架构。 https://arxiv.org/pdf/2001.08361.pdfhttps://arxiv.org/pdf/2001.08361.pdf 实验表明&#xff0c;测试损失与模型大小、数据集…

【软件工程】【22.04】p1

关键字&#xff1a; 软件需求规约基本性质、数据字典构成、内聚程度最高功能内聚、公有属性、RUP实体类、评审、测试序列、软件确认过程、CMMI能力等级 软件需求分类、DFD数据流图组成&#xff08;实体&#xff09;、经典详细设计、数据耦合、关联多重性、状态图、黑盒测试、…

『Z-Weekly Feed 08』加密资产观 | FHE应用前景 | OPAL协议

一位机构投资者的加密资产观 作者&#xff1a;Hongbo 01 &#x1f4a1;TL;DR 在加密投资领域如何找到真正的“价值”&#xff1a;Crypto 作为一种新兴资产&#xff0c;应该找到一种区别于传统公司股票资产的估值方法&#xff0c;本文重点阐述了加密货币作为新的资产类型与传统资…

全国实体商铺店铺商家采集工具,一键采集商家手机号,让你轻松找到目标客户

随着互联网的发展&#xff0c;越来越多的商家开始在网上开展业务&#xff0c;实体商铺的竞争也日益激烈。为了更好地吸引客户&#xff0c;很多商家都选择了线上推广和营销。然而&#xff0c;仅仅依靠线上推广是远远不够的&#xff0c;线下的实体商铺也需要积极拓展客源。因此&a…