十大排序总结之——冒泡排序、插入排序

同样,这两几乎也是被淘汰了的算法,尽管它们是稳定的,但是时间复杂度没人喜欢,了解一下就好,没啥好说的,注意最后一句话就行了

一,冒泡排序

1. 算法步骤

共n-1趟,谁两敢冒泡就换了谁两

第一趟,比较n-1次,每个相邻的位置都比较一次,比较两个元素大小,若位置反了就交换位置,一趟结束,最后一个位置就是最大值(降序就是最小值)

第二趟,比较n-2次,同上,最后一个元素不参与比较

第三趟,比较n-1次,同上,最后两个元素不参与比较

……

第n-1趟,比较1次,同上,最后n-2个元素不参与比较

一共比较累 1+2+3+……n-1 = (1 + n-1)*(n-1) / 2 = 1/2 * ( n^2 - n) ,比选择排序的n^2好一点点呵,然并……

2. 动图演示

3. 什么时候最快

当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

4. 什么时候最慢

当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

5、代码


template<typename T> void bubble_sort(T arr[], int len) {int i, j;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1])swap(arr[j], arr[j + 1]);
}

二、插入排序

1. 算法步骤

共n-1趟,把每一个元素都插入到(理论上)原本该在的位置上去

第一趟,把第一个元素看成已经排序好了的序列,用第2个元素来与之比较,比它大就插入到第一个后面,比它小就插入到它前面 (比较1次)

第二趟,把前2个元素看成已经排序好了的序列,用第3个元素来与前面的元素逐个比较,比某个比较元素大就插入到它后面,比它小就继续比较再前一个,若直到比第一个还小,就插入到第一个的位置(比较 1~2次)

第三趟,把前3个元素看成已经排序好了的序列,用第4个元素来与前面的元素逐个比较,比某个比较元素大就插入到它后面,比它小就继续比较再前一个,若直到比第一个还小,就插入到第一个的位置(比较1~3次)

………………………………

第n-1趟,把前n-1个元素看成已经排序好了的序列,最后 1 个元素来与前面的n-1元素逐个比较,比某个比较元素大就插入到它后面,比它小就继续比较再前一个,若直到比第一个还小,就插入到第一个的位置(比较1~n-1)

比冒泡排序更好一点了,

2. 动图演示


代码实现

void insertion_sort(int arr[],int len){for(int i=1;i<len;i++){int key=arr[i];int j=i-1;while((j>=0) && (key<arr[j])){arr[j+1]=arr[j];j--;}arr[j+1]=key;}
}

特别注意:

之所以说只说是几乎被淘汰了,而不是完全淘汰,是因为这两哥们的最好情况是O(n),还都是稳定的排序方法,在元素大部分都是有序的,只有极个别的位置错了的情况下,这两个算法的优势就来了,特别是插入排序,本来就是逐个插入到正确的位置上去,现在大部分都是有序的,这部相当于大部分都插入好了嘛,就剩下极个别插入一下就完事了对吧,这是其他任何排序算法都无法比拟的存在

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

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

相关文章

Stable Diffusion API入门:简明教程

Stable Diffusion 是一个先进的深度学习模型&#xff0c;用于创造和修改图像。这个模型能够基于文本描述来生成图像&#xff0c;让机器理解和实现用户的创意。使用这项技术的关键在于掌握其 API&#xff0c;通过编程来操控图像生成的过程。 在探索 Stable Diffusion API 的世界…

相机内参标定理论篇------相机模型选择

相机种类&#xff1a; 当拿到一款需要标定内参的相机时&#xff0c;第一个问题就是选择那种的相机模型。工程上相机类型的划分并不是十分严格&#xff0c;一般来说根据相机FOV可以把相机大概分为以下几类&#xff1a; 长焦相机&#xff1a;< 标准相机&#xff1a;~&…

2022年全国职业院校技能大赛(高职组)“云计算”赛项赛卷①第一场次:私有云

2022年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算”赛项赛卷1 第一场次&#xff1a;私有云&#xff08;30分&#xff09; 目录 2022年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算”赛项赛卷1 第一场次&#xff1a;私有云&#xff0…

千里马2023年终总结-android framework实战

背景&#xff1a; hi粉丝朋友们&#xff1a; 2023年马上就过去了&#xff0c;很多学员朋友也都希望马哥这边写个年终总结&#xff0c;因为这几个月时间都忙于新课程halsystracesurfaceflinger专题的开发&#xff0c;差点都忘记了这个事情了&#xff0c;今天特别花时间来写个bl…

最优化方法Python计算:无约束优化应用——神经网络回归模型

人类大脑有数百亿个相互连接的神经元&#xff08;如下图(a)所示&#xff09;&#xff0c;这些神经元通过树突从其他神经元接收信息&#xff0c;在细胞体内综合、并变换信息&#xff0c;通过轴突上的突触向其他神经元传递信息。我们在博文《最优化方法Python计算&#xff1a;无约…

SpringMVC框架

SpringMVC 三层架构MVC模式SpringMVC入门案例总结 三层架构 表现层&#xff08;web&#xff09; 页面数据的收集&#xff0c;产出页面 业务逻辑层&#xff08;service&#xff09; 业务处理 数据访问层&#xff08;Dao&#xff09; 数据持久化 MVC模式 SpringMVC 基于Java…

影视后期:PR 调色处理,灰片还原,校色偏色素材

灰片还原 确定拍摄灰片的相机型号品牌官网下载专用log文件LUT-浏览-导入slog3分析亮部波形-增加画面对比分析矢量示波器-提高整体饱和 校正LUT可以将前期拍摄的log色彩模式的视频转换为成709色彩模式&#xff0c;即将灰度视频转换为正常效果(灰片还原) 各个相机有对应的校正L…

开源预约挂号平台 - 从0到上线

文章目录 开源预约挂号平台 - 从0到上线演示地址源码地址可以学到的技术前端技术后端技术部署上线开发工具其他技术业务功能 项目讲解前端创建项目 - 安装PNPM - 使用VSCODE - 安装插件首页顶部与底部 - 封装组建 - 使用scss左右布局中间内容部分路由 - vue-routerBANNER- 走马…

RFC6749-OAuth2.0

前言 最近在项目中需要实现SSO(单点登录)功能,以实现一处注册,即可在任何平台之间登录的功能。我们项目中并没有直接对接第三方认证系统而是通过集成keycloak 完成一系类安全协议的对接工作。如果我们在代码级别自己完成各种安全协议的对接是一项十分大的工程。不仅要走统一的…

jsp介绍

JSP 一种编写动态网页的语言&#xff0c;可以嵌入java代码和html代码&#xff0c;其底层本质上为servlet,html部分为输出流&#xff0c;编译为java文件 例如 源jsp文件 <% page contentType"text/html; charsetutf-8" language"java" pageEncoding&…

Django 学习教程-介绍与安装

系列 Django 学习教程- Hello world入门案例-CSDN博客 介绍 Django 是一个由 Python 编写用于Web 应用程序开发的高级 Python Web 框架 Django 提供了一套强大的工具&#xff08;无需重新发明轮子&#xff09;&#xff0c;使得开发者能够快速构建 Web 网站。 Django 采用了…

【每日一题】收集巧克力

文章目录 Tag题目来源题目解读解题思路方法一&#xff1a;枚举操作数 写在最后 Tag 【枚举】【数组】【2023-12-28】 题目来源 2735. 收集巧克力 题目解读 有长度为 n, 下标从 0 开始的整数数组 nums, 表示收集不同类型的巧克力的成本. nums[i] 表示收集类型 i 巧克力的成本…

linux下docker搭建Prometheus +SNMP Exporter +Grafana进行核心路由器交换机监控

一、安装 Docker 和 Docker Compose https://docs.docker.com/get-docker/ # 安装 Docker sudo apt-get update sudo apt-get install -y docker.io# 安装 Docker Compose sudo apt-get install -y docker-compose二、创建配置文件及测试平台是否正常 1、选个文件夹作为自建…

simulink代码生成(六)——多级中断的配置

假如系统中存在多个中断&#xff0c;需要合理的配置中断的优先级与中断向量表&#xff1b;在代码生成中&#xff0c;要与中断向量表对应&#xff1b;中断相关的知识参照博客&#xff1a; DSP28335学习——中断向量表的初始化_中断向量表什么时候初始化-CSDN博客 F28335中断系…

WPF Button使用漂亮 控件模板ControlTemplate 按钮使用控制模板实例及源代码 设计一个具有圆角边框、鼠标悬停时颜色变化的按钮模板

续前两篇模板文章 模板介绍1 模板介绍2 WPF中的Button控件默认样式简洁&#xff0c;但可以通过设置模板来实现更丰富的视觉效果和交互体验。按钮模板主要包括背景、边框、内容&#xff08;通常为文本或图像&#xff09;等元素。通过自定义模板&#xff0c;我们可以改…

jmeter的常用功能及在测试中的基本使用和压测实战

Jmeter基础功能 了解Jmeter的常用组件 元件&#xff1a;多个类似功能组件的容器&#xff08;类似于类&#xff09; 一&#xff1a;Test Plan&#xff08;测试计划&#xff09; 测试计划通常用来给测试的项目重命名&#xff0c;使用多线程脚本运行时还可以配置线程组运行方式…

SQLSERVER排查CPU占用高

操作系统是Windows2008R2 ,数据库是SQL2008R2 64位 64G内存,16核CPU 硬件配置还是比较高的,他说服务器运行的是金蝶K3软件,数据库实例里有多个数据库 现象 他说是这几天才出现的,而且在每天的某一个时间段才会出现CPU占用高的情况 内存占用不太高,只占用了30个G CPU…

Java---网络编程

文章目录 1. 网络编程概述2. InetAddress3. 端口和协议4. Java网络API5. URL6. URLConnection类 1. 网络编程概述 1. 计算机网络&#xff1a;是指将地理位置不同的具有独立功能的多台计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统、网络管理软…

Java中利用Redis,ZooKeeper,数据库等实现分布式锁(遥遥领先)

1. 分布式锁 1.1 什么是分布式锁 在我们进行单机应用开发涉及并发同步的时候&#xff0c;我们往往采用synchronized或者ReentrantLock的方式来解决多线程间的代码同步问题。但是当我们的应用是在分布式集群工作的情况下&#xff0c;那么就需要一种更加高级的锁机制&#xff0…

音视频技术开发周刊 | 326

每周一期&#xff0c;纵览音视频技术领域的干货。 新闻投稿&#xff1a;contributelivevideostack.com。 全球最强「开源版Gemini」诞生&#xff01;全能多模态模型Emu2登热榜&#xff0c;多项任务刷新SOTA 最强的全能多模态模型来了&#xff01;就在近日&#xff0c;智源研究院…