C语言实现冒泡排序:从基础到优化全解析
一、什么是冒泡排序?
冒泡排序(Bubble Sort)是一种经典的排序算法,其工作原理非常直观:通过多次比较和交换相邻元素,将较大的元素“冒泡”到数组的末尾。经过多轮迭代,整个数组会变得有序。
二、冒泡排序的核心思想
-
比较相邻元素:
- 从数组的起始位置开始,逐个比较相邻的两个元素。
- 如果顺序不符合(如升序时前一个元素大于后一个元素),则交换两者的位置。
-
逐步缩小范围:
- 每一轮结束后,当前未排序部分中最大的元素会移动到正确的位置。
- 下一轮只需处理前面的未排序部分。
三、冒泡排序的实现步骤
- 从数组的第一个元素开始,与相邻元素进行比较。
- 如果顺序不对,交换这两个元素。
- 每轮操作后,将最大的元素固定在数组的最后。
- 重复上述步骤,直到数组完全有序。
四、冒泡排序的 C 语言实现
基本实现
以下是冒泡排序的基本实现代码:
#include <stdio.h>// 冒泡排序函数
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) { // 比较相邻元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}// 主函数
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");bubbleSort(arr, n);printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}
五、输入输出示例
输入
数组:[64, 34, 25, 12, 22, 11, 90]
输出
排序前的数组:64 34 25 12 22 11 90
排序后的数组:11 12 22 25 34 64 90
六、复杂度分析
- 时间复杂度:
- 最坏情况(完全逆序):( O(n^2) )
- 最好情况(已排序):( O(n^2) )(未优化情况下)。
- 空间复杂度:
- 只使用了常量空间,空间复杂度为 ( O(1) )。
- 稳定性:
- 冒泡排序是稳定的,因为它不会改变相等元素的相对顺序。
七、优化冒泡排序
1. 提前终止的优化
在某一轮比较中,如果没有发生交换,说明数组已经有序,可以提前结束排序。
void optimizedBubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int swapped = 0; // 标记变量for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = 1; // 标记发生了交换}}if (!swapped) break; // 如果没有发生交换,提前结束}
}
2. 双向冒泡排序(鸡尾酒排序)
普通冒泡排序每轮只向一个方向“冒泡”,双向冒泡则在一轮中从两端同时冒泡,缩小范围。
void cocktailSort(int arr[], int n) {int swapped = 1;int start = 0, end = n - 1;while (swapped) {swapped = 0;// 从左向右冒泡for (int i = start; i < end; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}if (!swapped) break;swapped = 0;end--;// 从右向左冒泡for (int i = end - 1; i >= start; i--) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}start++;}
}
八、优缺点分析
优点
- 实现简单:逻辑直观,代码易于编写和调试。
- 稳定性好:不会改变相等元素的相对顺序。
缺点
- 效率较低:时间复杂度较高,尤其对于大规模数据不适用。
- 优化潜力有限:即使优化后,性能仍不如快速排序或归并排序。
九、冒泡排序的适用场景
- 小规模数据排序:当数据量较小时,冒泡排序的性能尚可接受。
- 教学与学习:作为入门排序算法,帮助理解排序的基本思想。
- 特殊情况下的稳定性需求:当需要保持相等元素的相对顺序时,可优先选择冒泡排序。
十、总结与建议
冒泡排序作为最基础的排序算法,尽管效率较低,但其直观的实现方式非常适合初学者学习和理解排序算法的核心思想。在实际应用中,建议结合优化方法(如提前终止、双向冒泡)以提升性能。
下一步学习方向:
- 探索其他排序算法(如插入排序、选择排序、快速排序)。
- 理解排序算法的稳定性和复杂度,选择合适的算法解决实际问题。
- 实现冒泡排序的多种语言版本(如 Python、Java)。
相关文章:
C语言实现冒泡排序:从基础到优化全解析
一、什么是冒泡排序? 冒泡排序(Bubble Sort)是一种经典的排序算法,其工作原理非常直观:通过多次比较和交换相邻元素,将较大的元素“冒泡”到数组的末尾。经过多轮迭代,整个数组会变得有序。 二…...

windows11下git与 openssl要注意的问题
看了一下自己贴文的历史,有一条重要的忘了写了。 当时帮有位同事配置gitlab,众说周知gitlab是不太好操作。 但我还是自认自己git还是相当熟的。 解决了一系列问题,如配置代理,sshkey,私有库,等等࿰…...

lua除法bug
故事背景,新来了一个数值,要改公式。神奇的一幕出现了,公式算出一个非常大的数。排查是lua有一个除法bug,1除以大数得到一个非常大的数。 function div(a, b)return tonumber(string.format("%.2f", a/b)) end print(1/73003) pri…...

Ubuntu下Docker容器java服务往mysql插入中文数据乱码
一、问题描述 1、java服务部署在ubuntu下的docker容器内,但是会出现部分插入中文数据显示乱码,如图所示: 二、解决方案 1、查看mysql是否支持utf8,登录进入Mysql 输入命令: mysql -u root -pshow variables like c…...

C语言根据字符串变量获取/设置结构体成员值
一、背景 在项目中需要根据从数据库中获取的字段与对应的键值付给对应结构体成员上,而c语言中没有类似的反射机制,所以需要实现类似功能。例,从表中查到a 10,在结构体t中,需要将 t.a 10。 二、实现 感谢ChatGPT&…...

Selenium 自动化测试demo
场景描述: 模拟用户登录页面操作,包括输入用户名、密码、验证码。验证码为算数运算,如下: 使用到的工具和依赖: 1. Selenium:pip install selenium 2. 需要安装浏览器驱动:这里使用的是Edge 3…...
LeetCode 111.二叉树的最小深度
题目: 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 思路:自底向上(归)/自顶向下(递) DF…...

大工C语言作业答案
前言 这里是大连理工大学新版C语言课程MOOC作业的答案。 后期我会把全部的作业答案开源出来,希望对大家有帮助。 第九周第一题 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int B(int i) {int sum 1;while (i > 0){sum i * sum;i--;}return su…...

【Unity踩坑】Unity中父对象是非均匀缩放时出现倾斜或剪切现象
The game object is deformed when the parent object is in non-uniform scaling. 先来看一下现象 有两个Cube, Cube1(Scale2,1,1),Cube2(Scale1,1,1) 将Cube2拖拽为Cube2的子对象。并且将position设置为(-0.6,1,0&a…...
QT 跨平台实现 SSDP通信 支持多网卡
一.多网卡场景 在做SSDP通信的时候,客户端发出M-search命令后, 主机没有捕捉到SSDP的消息,你可以查看下,是不是局域网下,既打开了wifi,又连接了本地网络,mac os下很容易出现这种场景。此时,我们发送消息时,需要遍历所有网卡并发送M-search命令。 二.QT相关接口介绍 1…...

如何寻找适合的HTTP代理IP资源?
一、怎么找代理IP资源? 在选择代理IP资源的时候,很多小伙伴往往将可用率作为首要的参考指标。事实上,市面上的住宅IP或拨号VPS代理IP资源,其可用率普遍在95%以上,因此IP可用率并不是唯一的评判标准 其实更应该关注的…...

数据结构(ArrayList顺序表)
一、引言 1.什么是顺序表 定义: 顺序表是一种基于阵列实现的线性表结构,用连续的存储空间保存表中的数据元素,并按顺序排列。 底层依赖阵列,支持随机访问。元素之间没有额外的连接信息,如指针或链表节点。通过动态扩容…...

直接抄作业!Air780E模组LuatOS开发:位运算(bit)示例
在嵌入式开发中,位运算是一种高效且常用的操作技巧。本文将介绍如何使用Air780E模组和LuatOS进行位运算,并通过示例代码帮助读者快速上手。 一、位运算概述 位运算是一种在计算机系统中对二进制数位进行操作的运算。由于计算机内部数据的存储和处理都是…...
RK3588-LinuxSDK安装
安装依赖软件 执行如下命令,安装 LinuxSDK 开发包依赖软件。 备注:安装过程中,请保证 Ubuntu 可正常访问互联网,若提示"*** is already the newest version ***"表示该软件已安装,请忽略。 Host# sudo apt-get install -y git ssh make gcc libssl-dev \ liblz…...

MATLAB 中有关figure图表绘制函数设计(论文中常用)
在撰写论文时,使用 MATLAB 导出的图像常常因大小和格式不统一,导致投稿时编辑部频繁退稿,要求修改和调整。这不仅浪费时间,也增加了工作量。为了减少这些麻烦,可以在 MATLAB 中导出图像时提前设置好图表的大小、格式和…...
Unity UGUI原理剖析
UI最重要的两部分 UI是如何渲染出来的点击事件如何触发何时发生UI重绘 1:UI如何渲染出来的 UI渲染一定是有顶点的,没有顶点就没法确定贴图的采样,UGUI的顶点在一张Mesh上创建,经过渲染管线UI就渲染到屏幕上了,UI的渲染…...
Spring框架使用xml方式配置ThreadPoolTaskExecutor线程池,并且自定义线程工厂
一、自定义线程工厂 自定义线程工厂需要实现java.util.concurrent.ThreadFactory接口,重写newThread方法。 示例代码: package com.xiaobai.thread;import org.apache.log4j.Logger;import java.util.concurrent.ThreadFactory; import java.util.conc…...

架构-微服务-服务网关
文章目录 前言一、网关介绍1. 什么是API网关2. 核心功能特性3. 解决方案 二、Gateway简介三、Gateway快速入门1. 基础版2. 增强版3. 简写版 四、Gateway核心架构1. 基本概念2. 执行流程 五、Gateway断言1. 内置路由断言工厂2. 自定义路由断言工厂 六、过滤器1. 基本概念2. 局部…...

基于springboot的HttpClient、OKhttp、RestTemplate对比
HttpClient详细 Httpclient基础!!!!实战训练!!!!-CSDN博客 OKhttp使用 OKhttp导包 <!-- ok的Http连接池 --><dependency><groupId>com.squareup.okhttp3</g…...

(计算机组成原理)期末复习
第一章 计算机的基本组成:硬件软件(程序)计算机系统 软件有系统软件(系统管理工具),应用软件 计算机硬件:包括主机和外设,主机包括CPU和内存,***CPU由运算器和控制器所组…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...