【C语言】全面解析冒泡排序

文章目录

        • 什么是冒泡排序?
        • 冒泡排序的基本实现
        • 代码解释
        • 冒泡排序的优化
        • 冒泡排序的性能分析
        • 冒泡排序的实际应用
        • 结论

在这里插入图片描述

在C语言编程中,排序算法是一个非常基础且重要的概念。冒泡排序作为最简单、最易理解的排序算法之一,广泛应用于各种编程教学和实践中。本文将全面解析C语言中的冒泡排序算法,包括其定义、实现、优化方法和性能分析,帮助读者深入理解这一经典算法。

什么是冒泡排序?

冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复遍历待排序的序列,依次比较相邻元素并交换它们的位置,使较大的元素逐渐“冒泡”到序列的末端。冒泡排序的核心思想是通过不断的比较和交换,将未排序的元素逐步移到正确的位置。

冒泡排序的基本实现

以下是冒泡排序的基本实现代码:

#include <stdio.h>// 冒泡排序函数
void bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n-1; i++) {for (j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// 交换arr[j]和arr[j+1]temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}// 打印数组函数
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}// 主函数
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr)/sizeof(arr[0]);printf("未排序的数组: \n");printArray(arr, n);bubbleSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}
代码解释
  1. 冒泡排序函数bubbleSort

    • 使用两个嵌套的for循环遍历数组。
    • 内层循环用于比较和交换相邻元素,确保较大的元素逐步移到序列末端。
    • 外层循环用于重复上述过程,直到所有元素都排序完成。
  2. 打印数组函数printArray

    • 遍历数组并打印每个元素,便于查看排序结果。
  3. 主函数main

    • 初始化一个整数数组并计算其大小。
    • 调用bubbleSort函数对数组进行排序。
    • 打印排序前后的数组。
冒泡排序的优化

虽然冒泡排序简单易懂,但其效率较低。以下是几种常见的优化方法:

  1. 标志位优化

    • 使用一个标志位swapped来检测是否发生交换,如果一轮排序中没有发生交换,则说明数组已经有序,可以提前结束排序。

    优化代码示例:

    void bubbleSort(int arr[], int n) {int i, j, temp;int swapped;for (i = 0; i < n-1; i++) {swapped = 0;for (j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// 交换arr[j]和arr[j+1]temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = 1;}}// 如果没有发生交换,提前结束排序if (swapped == 0)break;}
    }
    
  2. 双向冒泡排序(鸡尾酒排序)

    • 冒泡排序的另一种改进方法是双向冒泡排序,也称为鸡尾酒排序。该算法在一次遍历中同时从左向右和从右向左进行比较和交换,进一步减少了排序的回合数。

    双向冒泡排序代码示例:

    void cocktailSort(int arr[], int n) {int swapped = 1;int start = 0;int end = n - 1;int i, temp;while (swapped) {swapped = 0;// 从左向右冒泡for (i = start; i < end; ++i) {if (arr[i] > arr[i + 1]) {temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}// 如果没有发生交换,提前结束排序if (!swapped)break;// 减少尾部已排序元素--end;swapped = 0;// 从右向左冒泡for (i = end - 1; i >= start; --i) {if (arr[i] > arr[i + 1]) {temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = 1;}}// 增加头部已排序元素++start;}
    }
    
冒泡排序的性能分析

冒泡排序的时间复杂度在最坏情况下为 O ( n 2 ) O(n^2) O(n2),这是因为每次排序都需要比较和交换相邻元素。在最好情况下(当数组已经有序时),时间复杂度为 O ( n ) O(n) O(n),这得益于标志位优化。然而,冒泡排序的平均时间复杂度仍为 O ( n 2 ) O(n^2) O(n2),因此在处理大型数据集时效率较低。

冒泡排序的空间复杂度为 O ( 1 ) O(1) O(1),因为它只需要常数级别的额外空间来存储临时变量。冒泡排序是一个稳定的排序算法,因为相同元素的相对位置不会改变。

冒泡排序的实际应用

虽然冒泡排序在处理大型数据集时效率较低,但它在以下几种情况下仍然有用:

  1. 教学和演示

    • 冒泡排序算法简单易懂,非常适合作为初学者学习排序算法的入门教材。
  2. 小型数据集

    • 在处理小型数据集时,冒泡排序的性能足够,而且实现简单。
  3. 需要稳定排序的场景

    • 在某些需要稳定排序的场景中,冒泡排序可以确保相同元素的相对位置不变。
结论

冒泡排序是C语言中最基础的排序算法之一,其实现简单且易于理解。尽管它的效率不高,但通过标志位优化和双向冒泡排序等方法,可以在一定程度上提升其性能。在学习和使用冒泡排序时,了解其优缺点以及适用场景,能够帮助我们更好地选择和使用排序算法。希望本文能帮助读者深入理解冒泡排序,并在实际编程中灵活应用。

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

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

相关文章

vi 编辑器快捷生成 main 函数和基本框架

step1: 执行 sudo vi /etc/vim/vimrc &#xff08;修改vimrc需要管理员权限&#xff1a;sudo&#xff09; step2:输入用户密码&#xff0c;回车, 编辑vimrc文件 step3:在尾行输入以下代码&#xff08;可复制&#xff09; map mf i#include<stdio.h><ESC>o#includ…

.net dataexcel 脚本公式 函数源码

示例如: ScriptExec(""sum(1, 2, 3, 4)"") 结果等于10 using Feng.Excel.Builder; using Feng.Excel.Collections; using Feng.Excel.Interfaces; using Feng.Script.CBEexpress; using Feng.Script.Method; using System; using System.Collections.Gen…

Gitee 使用教程1-SSH 公钥设置

一、生成 SSH 公钥 1、打开终端&#xff08;Windows PowerShell 或 Git Bash&#xff09;&#xff0c;通过命令 ssh-keygen 生成 SSH Key&#xff1a; ssh-keygen -t ed25519 -C "Gitee SSH Key" 随后摁三次回车键&#xff08;Enter&#xff09; 2、查看生成的 SSH…

探索Puppeteer的强大功能:抓取隐藏内容

背景/引言 在现代网页设计中&#xff0c;动态内容和隐藏元素的使用越来越普遍&#xff0c;这些内容往往只有在特定的用户交互或条件下才会显示出来。为了有效地获取这些隐藏内容&#xff0c;传统的静态爬虫技术往往力不从心。Puppeteer&#xff0c;作为一个强大的无头浏览器工…

【Git】Git Submodules 介绍(通俗易懂,总结了工作完全够用的 submodule 命令)

Git Submodules 介绍 1、为什么你值得读这篇文章&#xff1f;2、为什么有 submodules&#xff1f;3、了解 Git Submodules3.1、如何让一个Git仓库变为另一个Git仓库的 submodule3.2、submodule 的父子关系存在哪里3.3、submodule 的父子关系信息怎么存 4、submodule 开发常用操…

昇思25天学习打卡营第30天 | MindNLP ChatGLM-6B StreamChat

今天是第30天&#xff0c;学习了MindNLP ChatGLM-6B StreamChat。 今天是参加打卡活动的最后一天&#xff0c;经过这些日子的测试&#xff0c;昇思MindSpore效果还是不错的。 ChatGLM-6B 是一个开源的、支持中英双语的对话语言模型&#xff0c;具有62亿参数&#xff0c;基于 …

vue3前端开发-小兔鲜项目-人气推荐栏目的前端渲染

vue3前端开发-小兔鲜项目-人气推荐栏目的前端渲染&#xff01;今天和大家分享一下&#xff0c;人气推荐栏目的前端页面如何渲染内容。 经历过上一次的&#xff0c;新鲜好物的栏目渲染之后&#xff0c;我们已经熟练了&#xff0c;vue3的接口调用&#xff0c;数据渲染到页面中的整…

【Android安全】Ubuntu 下载、编译 、刷入Android-8.1.0_r1

0. 环境准备 Ubuntu 16.04 LTS&#xff08;预留至少95GB磁盘空间&#xff0c;实测占94.2GB&#xff09; Pixel 2 XL 要买欧版的&#xff0c;不要美版的。 欧版能解锁BootLoader、能刷机。 美版IMEI里一般带“v”或者"version"&#xff0c;这样不能解锁BootLoader、…

acwing796-子矩阵的和-前缀和

s矩阵是全局变量&#xff0c;维度n*m,从1~n和 1~m存储元素【0】【0】~【0】【m】和【0】【0】~【n】【0】分别存储的都是0.s矩阵刚开始是存储输入的元素&#xff0c;后面用于存储前缀和。 s矩阵的意思是s【i】【j】表示从【0】【0】到【i】【j】为对角线的矩阵里面所有元素的和…

使用 Flask 3 搭建问答平台(三):注册页面模板渲染

前言 前端文件下载 链接https://pan.baidu.com/s/1Ju5hhhhy5pcUMM7VS3S5YA?pwd6666%C2%A0 知识点 1. 在路由中渲染前端页面 2. 使用 JinJa 2 模板实现前端代码复用 一、auth.py from flask import render_templatebp.route(/register, methods[GET]) def register():re…

Unity XR Interaction Toolkit的安装(二)

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神不吝指教&#xff01; 文章目录 前言一、安装1.打开unity项目2.打开包管理器&#xff08;PackageManage&#xff09;3.导入Input System依赖包4.Interaction Layers unity设置总结 前言 安装前请注意&#xff1a;需要…

JVM(day2)经典垃圾收集器

经典垃圾收集器 Serial收集 使用一个处理器或一条收集线程去完成垃圾收集工作&#xff0c;更重要的是强调在它进行垃圾收集时&#xff0c;必须暂停其他所有工作线程&#xff0c;直到它收集结束。 ParNew收集器 ParNew 收集器除了支持多线程并行收集之外&#xff0c;其他与 …

Redis 关于内存碎片的解决方法

今天生产机报内存爆满异常被叫过去查看问题&#xff0c;通过各种排除最终定位到了Redis的内存碎片的问题&#xff0c;这篇博客将详细介绍Redis内存碎片问题并给出最佳实践解决此问题。 Redis的内存碎片原理 先引用Redis官方的原话&#xff1a; 当键被删除时&#xff0c;Redis …

类和对象(二)

默认成员函数 默认成员函数就是用户没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。 C有六个默认成员函数&#xff0c;不写的情况下编译器会默认⽣成以下6个默认成员函数&#xff0c;最重要的是前4个&#xff0c;最后两个了解⼀下即可。另外&#xff…

Java垃圾收集器选择与优化策略

1.垃圾收集算法有哪些,可以聊一下吗? 如何确定一个对象是垃圾? 要想进行垃圾回收,得先知道什么样的对象是垃圾。 1.1 引用计数法 对于某个对象而言,只要应用程序中持有该对象的引用,就说明该对象不是垃圾。如果一个对象没有任何指针对其引用,它就是垃圾。 弊端:如果…

成像光谱遥感技术中的AI革命:ChatGPT

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力&#xff0c;ChatGPT在遥感中的应用&#xff0c;人工智能在…

LeetCode 232.用栈实现队列 C写法

LeetCode 232.用栈实现队列 C写法 思路&#x1f9d0;&#xff1a; 栈代码在本篇中。与队列实现栈类似&#xff0c;不过这里我们建立两个栈&#xff0c;一个栈专门存放入队数据&#xff0c;一个专门存放出队数据&#xff0c;不需要再来回导数据。原理在于一个栈的数据到另一个栈…

安卓逆向入门(2)------Xpose初级

项目配置 在AndroidMainfest.xml中添加 <meta-dataandroid:name"xposedmodule"android:value"true" /><meta-dataandroid:name"xposeddescription"android:value"Xposed模块初体验" /><meta-dataandroid:name"xp…

python爬虫获取网易云音乐评论歌词以及歌曲地址

python爬虫获取网易云音乐评论歌词以及歌曲地址 一.寻找数据接口二.对负载分析三.寻找参数加密过程1.首先找到评论的请求包并找到发起程序2.寻找js加密的代码 四.扣取js的加密源码1.加密函数参数分析①.JSON.stringify(i0x)②bse6Y(["流泪", "强"])③bse6Y…

算法日记day 11(KMP算法)

一、KMP算法 基本原理&#xff1a; KMP算法&#xff08;Knuth-Morris-Pratt算法&#xff09;是一种用于在一个文本串&#xff08;字符串&#xff09;中查找一个模式串&#xff08;子串&#xff09;的高效算法。它的主要优点是在匹配过程中避免了回溯&#xff08;backtracking…