当前位置: 首页 > news >正文

八大排序(二)--------冒泡排序

本专栏内容为:八大排序汇总 通过本专栏的深入学习,你可以了解并掌握八大排序以及相关的排序算法。

💓博主csdn个人主页:小小unicorn
⏩专栏分类:八大排序汇总
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

无论你学习哪种编程语言,在学到循环和数组时,通常都会介绍一种排序算法来作为例子,而这个算法一般就是冒泡排序。并不是它的名称很好听,而是说这个算法的思路最简单,最容易理解。因此,哪怕大家可能都已经学过冒泡排序了,我们还是从这个算法开始我们的排序之旅

在这里插入图片描述

冒泡排序

  • 最简单排序的实现
  • 冒泡排序算法
  • 冒泡排序优化
  • 冒泡排序复杂度分析

在这里插入图片描述

最简单排序的实现

冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

冒泡的实现在细节上可以有很多种变化,我们将分别就3种不同的冒泡实现代码,来讲解冒泡排序的思想。这里,我们就先来看看比较容易理解的一段。

注意:排序用到的结构与函数在第一部分:排序的基本概念与分类。我们已经实现。详情请点击:八大排序(一)--------排序的基本概念与分类


//对顺序表L作交换排序(冒泡排序初级版本)
void BubbleSort0(SqList* L)
{int i = 0, j = 0;for (i = 1; i < L->length; i++){for (j = i+1; j <= L->length; j++){if (L ->r[i] > L->r[j]){swap(L, i, j);   //交换L->r[i]与r->[j]}}}
}

这段代码严格意义上说,不算是标准的冒泡排序算法,因为它不满足“两两比较相邻记录”的冒泡排序思想,它更应该是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在一次循环后一定变成最小值。

如下图所示,假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
当i=1时,9与1交换后,在第一位置的1与后面的关键字比较都小,因此它就是最小值。

当i=2时,第二位置先后由9换成5,换成3,换成2,完成了第二小的数字交换。后面的数字变换类似,这里不再介绍。

这应该算是最容易写出的排序代码了,不过这个简单易懂的代码,却是有缺陷的。观察后发现,在排序好1和2的位置后,对其余关键字的排序没有什么帮助(数字3反而还被换到了最后一位)。也就是说,这个算法的效率是非常低的。
在这里插入图片描述

冒泡排序算法

我们来看看正宗的冒泡算法,有没有什么改进的地方。


//对顺序表L作冒泡排序
void BubbleSort(SqList* L)
{int i = 0, j = 0;for (i = 1; i < L->length; i++){for (j = L->length-1; j >= i; j--)    //j从后往前循环{if (L->r[i] > L->r[j+1])          //若前者大于后者{swap(L, i, j+1);   //交换L->r[i]与r->[j+1]的值}}}
}

依然假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}

当i=1时,变量j由8反向循环到1,逐个比较,将较小值交换到前面,直到最后找到最小值放置在了第1的位置。

如下图所示,当i=1,j=8时,我们发现6>2,因此交换了它们的位置,j=7时,4>2,所以交换……直到=2时,因为1<2,所以不交换。j=1时,9>1,交换,最终得到最小值1放置第1的位置。

事实上,在不断循环的过程中,除了将关键字1放到第1的位置,我们还将关键字2从第9位置提到了第3的位置,显然这一算法比前面的要有进步,在上十万条数据的排序过程中,这种差异会体现出来。图中较小的数字如同气泡般慢慢浮到上面,因此就将此算法命名为冒泡算法。
在这里插入图片描述
后面的数字变换就很简单,这里就不在叙述了。

冒泡排序优化

这样的冒泡程序是否还可以优化呢?答案是肯定的。试想一下,如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}也就是说,除了第1和第2的关键字需要交换外,别的都已经是正常的顺序。

当i=1时,交换了2和1,此时序列已经有序,但是算法仍然不依不饶地将i=2~9以及每个循环中的循环都执行了一遍,尽管并没有交换数据,但是之后的大量比较还是大大地多余了,如下图所示。
在这里插入图片描述
当i=2时,我们已经对9与8,8与7,…,3与2作了比较,没有任何数据交换,这就说明此序列已经有序,不需要再继续后面的循环判断工作了。为了实现这个想法,我们需要改进一下代码,增加一个标记变量flag来实现这一算法的改进。

//对顺序表L作冒泡排序(改进版本)
void BubbleSort(SqList* L)
{int i = 0, j = 0;status flag = 1;                          //用flag进行标记for (i = 1; i < L->length && flag; i++)   //若flag为1则有效数据交换{flag = 0;for (j = L->length-1; j >= i; j--)    //j从后往前循环{if (L->r[i] > L->r[j+1])          //若前者大于后者{swap(L, i, j+1);              //交换L->r[i]与r->[j+1]的值flag = 1;                     //如果有数据交换,则flag为1}}}
}

代码改动的关键就是在变量的for循环中,增加了对flag是否为1的判断。

经过这样的改进,冒泡排序在性能上就有了一些提升,可以避免已经有序的情况下的无意义循环判断

冒泡排序复杂度分析

分析一下它的时间复杂度

最好的情况,也就是要排序的表本身就是有序的,那么我们比较次数,根据最后改进的代码,可以推断出就是n-1次的比较,没有数据交换,时间复杂度为O(n)。

最坏的情况,即待排序表是逆序的情况,此时需要比较之 ∑ i = 2 n ( i − 1 ) = 1 + 2 + 3 + … + ( n − 1 ) = n ( n − 1 ) / 2 \sum_{i=2}^n (i-1)=1+2+3+…+(n-1)=n(n-1)/2 i=2n(i1)=1+2+3++(n1)=n(n1)/2次,并作等数量级的记录移动。因此,总的时间复杂度为O(n2)。

相关文章:

八大排序(二)--------冒泡排序

本专栏内容为&#xff1a;八大排序汇总 通过本专栏的深入学习&#xff0c;你可以了解并掌握八大排序以及相关的排序算法。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;八大排序汇总 &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库…...

SmartSQL 一款开源的数据库文档管理工具

建议直接蓝奏云下载安装 蓝奏云下载&#xff1a;https://wwoc.lanzoum.com/b04dpvcxe 蓝奏云密码&#xff1a;123 项目介绍 SmartSQL 是一款方便、快捷的数据库文档查询、导出工具&#xff01;从最初仅支持 数据库、CHM文档格式开始&#xff0c;通过不断地探索开发、集思广…...

代码随想录算法训练营第56天 | ● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 动态规划之编辑距离总结篇

文章目录 前言一、583. 两个字符串的删除操作二、72. 编辑距离三、动态规划之编辑距离总结篇总结 前言 一、583. 两个字符串的删除操作 两种思路&#xff1a;1.直接动态规划&#xff0c;求两个字符串需要删除的最小次数 2.采用子序列的和-最长公共子序列。思路一分析如下&#…...

矩阵 m * M = c

文章目录 题1题2 题1 (2023江苏领航杯-prng) 题目来源&#xff1a;https://dexterjie.github.io/2023/09/12/%E8%B5%9B%E9%A2%98%E5%A4%8D%E7%8E%B0/2023%E9%A2%86%E8%88%AA%E6%9D%AF/ 题目描述&#xff1a; (没有原数据&#xff0c;自己生成的数据) from Crypto.Util.number…...

Linux——IO

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;Linux——文件系统 ☂️<3>开发环境&#xff1a;Centos7 &#x1f4ac;<4>前言&#xff1a;是不是只有C/C有文件操作呢&#xff1f;python&#xff0c;java&…...

svn(乌龟svn)和SVN-VS2022插件(visualsvn) 下载

下载地址: https://www.visualsvn.com/visualsvn/download/...

开源日报 0824 | 构建UI组件和页面的前端工作坊

Storybook 是一个用于构建 UI 组件和页面的前端工作坊&#xff0c;支持多种主流框架&#xff0c;提供丰富的插件&#xff0c;具有可配置性强和扩展性好的特点。 storybookjs/storybook Stars: 79.9k License: MIT Storybook 是一个用于构建 UI 组件和页面的前端工作坊&#x…...

福建三明大型工程机械3D扫描工程零件三维建模逆向抄数-CASAIM中科广电

高精度3D扫描技术已经在大型工件制造领域发挥着重要作用&#xff0c;可以高精度高效率实现全尺寸三维测量&#xff0c;本期&#xff0c;我们要分享的应用是大型工程机械3D扫描案例。 铣轮是深基础施工领域内工法先进、技术复杂程度高、高附加值的地连墙设备&#xff0c;具有成…...

使用香橙派学习 Linux的守护进程

Q&#xff1a;什么是守护进程 A&#xff1a;Linux Daemon&#xff08;守护进程&#xff09;是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行 某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务&#xff0c;不是对整个系统就是对某个…...

数据治理-数据仓库和商务智能

数据仓库的作用 减少数据冗余&#xff0c;提高信息一致性&#xff0c;让企业能够利用数据做出更优决策的方法&#xff0c;数据仓库是企业数据管理的核心。 业务驱动因素 运营支持职能、合规需求&#xff08;历史数据响应&#xff09;和商务智能活动&#xff08;主因&#xff1…...

CH2--x86系统架构概览

2.1 OVERVIEW OF THE SYSTEM-LEVEL ARCHITECTURE 图中的实线箭头表示线性地址&#xff0c;虚线表示段选择器&#xff0c;虚线箭头表示物理地址 2.1.1 Global and Local Descriptor Tables 全局描述符表 (GDT) GDT是一个全局的段描述符表&#xff0c;它存储在系统内存中的一个固…...

Immutable.js API 简介

Immutable-js 这个库的实现是深拷贝还是浅拷贝&#xff1f;immutable 来源immutable.js三大特性&#xff1a; 持久化数据结构结构共享惰性操作 Immutable.js 的几种数据类型 immutable 使用 使用 npm 安装 immutable&#xff1a; 常用API介绍 MapListList.isList() 和 Map.isMa…...

HLSL 入门(一)

HLSL High Level Shader Language 高级着色语言&#xff0c;是Direct3D中用来编写Shader的语言。其语法类似于C语言。 虽然其主要作用是用来编写例如顶点着色器&#xff0c;像素着色器。但本质是对图形并行管线进行编程&#xff0c;因此也能用来编写用于计算的着色器&#xff…...

【Docker】挂载数据卷

一、Docker数据卷说明及操作 在Docker中挂载数据卷是一种将数据持久化保存的方法&#xff0c;以便容器之间或容器与主机之间共享数据。以下是如何在Docker中挂载数据卷的步骤&#xff1a; 1、创建数据卷 首先&#xff0c;您需要创建一个数据卷。可以使用以下命令创建一个数据卷…...

[技术干货]spring 和spring boot区别

Spring 和 Spring Boot 都是 Java 框架&#xff0c;用于构建企业级应用程序。Spring 是一个完整的框架&#xff0c;提供各种功能&#xff0c;包括依赖注入、事务管理、数据访问、Web 开发等。Spring Boot 是一个基于 Spring 的框架&#xff0c;旨在简化 Spring 应用程序的开发和…...

【hudi】数据湖客户端运维工具Hudi-Cli实战

数据湖客户端运维工具Hudi-Cli实战 help hudi:student_mysql_cdc_hudi_fl->help AVAILABLE COMMANDSArchived Commits Commandtrigger archival: trigger archivalshow archived commits: Read commits from archived files and show detailsshow archived commit stats: …...

RK3588 添加ROOT权限

一.ROOT简介 ROOT权限是Linux和Unix系统中的超级管理员用户帐户&#xff0c;该帐户拥有整个系统的最高权利&#xff0c;可以执行几乎所有操作。ROOT就是获取安卓系统中的最高用户权限&#xff0c;以便执行一些需要高权限才能执行的操作(包括卸载系统自带程序、刷机、备份、还原…...

【云原生】k8s-----集群调度

目录 1.k8s的list-watch机制 1.1 list-watc机制简介 1.2 根据list-watch机制&#xff0c;pod的创建流程 2.scheduler的调度策略 2.1 scheduler的调度策略简介 2.2 Scheduler预选策略的算法 2.3 Scheduler优选策略的算法 3. k8s中的标签管理及nodeSelector和nodeName的 调…...

一键集成prometheus监控微服务接口平均响应时长

一、效果展示 二、环境准备 prometheus + grafana环境 参考博文:https://blog.csdn.net/luckywuxn/article/details/129475991 三、导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter...

2023/9/13 -- C++/QT

作业&#xff1a; 1> 将之前定义的栈类和队列类都实现成模板类 栈&#xff1a; #include <iostream> #define MAX 40 using namespace std;template <typename T> class Stack{ private:T *data;int top; public:Stack();~Stack();Stack(const Stack &ot…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Python爬虫实战:研究Restkit库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...

2025 后端自学UNIAPP【项目实战:旅游项目】7、景点详情页面【完结】

1、获取景点详情的请求【my_api.js】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http(/login/getWXSessionKey, {code,avatar}); };//…...

XXE漏洞知识

目录 1.XXE简介与危害 XML概念 XML与HTML的区别 1.pom.xml 主要作用 2.web.xml 3.mybatis 2.XXE概念与危害 案例&#xff1a;文件读取&#xff08;需要Apache >5.4版本&#xff09; 案例&#xff1a;内网探测&#xff08;鸡肋&#xff09; 案例&#xff1a;执行命…...

Springboot多数据源配置实践

Springboot多数据源配置实践 基本配置文件数据库配置Mapper包Model包Service包中业务代码Mapper XML文件在某些复杂的业务场景中,我们可能需要使用多个数据库来存储和管理不同类型的数据,而不是仅仅依赖于单一数据库。本技术文档将详细介绍如何在 Spring Boot 项目中进行多数…...