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

排序基础之插入排序

目录

前言

一、什么是插入排序

二、实现插入排序

三、插入排序优化

四、插入排序的特性


前言

上一篇中我们说到了《排序基础之选择排序》,这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。

一、什么是插入排序

简单来说就是:每次只处理一个元素,把这个元素插入到前面已经排好序的元素中,即:arr[0,i)已排好序,arr[i...n)未排序,把arr[i]放到合适的位置,比如:

实现思想:双层循环,外层循环i从下标0开始遍历,内层循环j从下标i处开始遍历,将下标j和下标j-1处的两个元素进行比较,如果下标j位置处的元素比下标j-1位置处的元素小,则将二者交换位置,然后下标j继续减1向左比较它的前一个元素,直到下标j所在位置元素不大于下标j-1处的元素,则跳出该层循环,依次类推,直至排序完成。

二、实现插入排序

下面我们通过代码来实现这个排序的过程:

public class InsertSort {public static void main(String[] args) {Integer[] arr = {6, 4, 2, 3, 1, 5};InsertSort.sort(arr);for (int ele : arr) {System.out.print(ele + " ");}System.out.println();Student[] students = {new Student("张三", 89),new Student("李四", 98),new Student("王五", 60)};InsertSort.sort(students);for (Student s : students) {System.out.println(s);}}private InsertSort() {}public static <T extends Comparable<T>> void sort(T[] arr) {// 将arr[i]插入到合适的位置for (int i = 0; i < arr.length; i++) {for (int j = i; j - 1 >= 0; j--) {if (arr[j].compareTo(arr[j - 1]) < 0) {swap(arr, j, j - 1);} else {break;}}}}private static <T> void swap(T[] arr, int i, int j) {T temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

运行结果如下:

三、插入排序优化

同样来看上面说到的这个数组[6,4,2,3,1,5],假如我们要对3这个元素它所在的位置进行排序,当前数组应该是:

我们上面的实现方式是用3这个元素不断的与它之前的元素进行位置的交换,要知道一次位置交换实际上进行了3次的操作,如果数据量很大的话,这个影响还是有的。现在我们想要对这种方式进行一定的优化,我们可以采用赋值的方式进行优化,思想就是:使用一个变量暂存元素3,然后进行元素比较时,如果前一个元素比3大,则直接把原来3所在位置的元素赋值为6,然后继续再比较前一个元素,直到找到对应的位置之后,将该位置的元素赋值为之前变量暂存的元素,这个流程实际上并未进行元素的交换,而是进行了元素的平移。

下面直接用代码来实现一下:

四、插入排序的特性

从上面的示例及代码中我们可以得到如下特性:

对于有序数组,插入排序的复杂度是O(n)的

但是对于整体来说,插入排序的复杂度仍然是O(n^2)的,有序数组是一种特殊情况

选择排序的复杂度永远是O(n^2)的 

OK,到这里我们关于插入排序的内容就介绍的差不多了,下期再会吧!

祝:工作顺利!

相关文章:

排序基础之插入排序

目录 前言 一、什么是插入排序 二、实现插入排序 三、插入排序优化 四、插入排序的特性 前言 上一篇中我们说到了《排序基础之选择排序》&#xff0c;这一篇我们来学习一下排序算法中的另一种基础排序算法——插入排序。 一、什么是插入排序 简单来说就是&#xff1a;每…...

LabVIEW控制DO通道输出一个精确定时的数字波形

LabVIEW控制DO通道输出一个精确定时的数字波形如何使用数据采集板卡的DO通道输出一个精确定时的数字波形&#xff1f;解答:产生一个数字波形首先需要创建一个布尔数组&#xff0c;把波形序列信息放到该布尔数组中&#xff0c;然后通过一个布尔数组至数字转换vi来产生数字波形。…...

openpnp - 零碎记录

文章目录openpnp - 零碎记录概述笔记配置文件保存无效必须在查找问题之后, 才能保存配置文件如果想找出配置动作引起的配置内容变化, 还是要尝试保存后, 比对变化才行ENDopenpnp - 零碎记录 概述 这段时间, 正在配置校准手头的openpnp设备, 用的官网最新的openpnp2.0. 由于o…...

Qt编写微信支付宝支付

文章目录一 微信支付配置参数二 支付宝支付配置参数三 功能四 Demo效果图五 体验地址一 微信支付配置参数 微信支付API&#xff0c;需要三个基本必填参数。 微信公众号或者小程序等的appid&#xff1b;微信支付商户号mchId&#xff1b;微信支付商户密钥mchKey&#xff1b; 具…...

LeetCode 剑指 Offer 64. 求1+2+…+n

求 12…n &#xff0c;要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句&#xff08;A?B:C&#xff09;。 示例 1&#xff1a; 输入: n 3 输出: 6 限制&#xff1a; 1 < n < 10000 解法一&#xff1a;利用逻辑运算符的短路&#xf…...

Mapper代理开发

MyBatis快速开发https://blog.csdn.net/weixin_51882166/article/details/129204439?spm1001.2014.3001.5501 使用Mapper代理方式完成 定义与SQL映射文件同名的Mapper接口 &#xff0c;将Mapper接口和SQL映射文件放置同一目录结构 新建接口和包&#xff1a; 将Mapper接口和…...

为什么在连接mysql时,设置 SetConnMaxIdleTime 没有作用

目录测试1go 1.15.15go 1.17.12测试2go 1.15.15go 1.17.12参考在使用golang 连接 mysql时&#xff0c;为了节省连接资源&#xff0c;在连接使用过后&#xff0c;希望在指定长度时间不再使用后&#xff0c;自动关闭连接。 这时&#xff0c;经常会使用SetConnMaxLifetime()&#…...

嵌入式开发利器

前言 俗话说&#xff0c;工欲善其事必先利其器&#xff0c;做嵌入式开发首先需要选择好的工具&#xff0c;对的工具&#xff0c;工具选对了能事半功倍&#xff0c;节省很多时间&#xff0c;那些开发大佬一般都会使用各种各样的工具&#xff0c;不同的环节使用不同的工具&#…...

Qt 的QString类的使用

Qt的QString类提供了很方便的对字符串操作的接口。 使某个字符填满字符串&#xff0c;也就是说字符串里的所有字符都有等长度的ch来代替。 QString::fill ( QChar ch, int size -1 ) 例&#xff1a; QString str "Berlin";str.fill(z);// str "zzzzzz"…...

django项目部署(腾讯云服务器centos)

基本步骤&#xff1a; 购买腾讯云服务器并配配置好 >> 本地项目依赖收集准备 >> 上传项目等文件到服务器 >> 服务器安装部署软件和python环境 >> 开始部署&#xff08;全局来看就这5个步骤&#xff09; 目录 目录 1. 购买腾讯云服务器并配配置好 …...

计算机网络笔记、面试八股(一)——TCP/IP网络模型

Note&#xff1a;【计算机网络笔记、面试八股】系列文章共计5篇&#xff0c;现已更新3篇&#xff0c;剩余2篇&#xff08;TCP连接、Web响应&#xff09;会尽快更新&#xff0c;敬请期待&#xff01; 本章目录1. TCP/IP网络模型1.1 应用层1.1.1 应用层作用1.1.2 应用层有哪些常用…...

51单片机入门 - 简短的位运算实现扫描矩阵键盘

介绍 例程使用 SDCC 编译、 stcgal 烧录&#xff0c;如果你想要配置一样的环境&#xff0c;可以参考本专栏的第一篇文章“51单片机开发环境搭建 - VS Code 从编写到烧录”&#xff0c;我的设备是 Windows 10&#xff0c;使用普中51单片机开发板&#xff08;STC89C52RC&#xf…...

Mr. Cappuccino的第45杯咖啡——Kubernetes之部署SpringBoot项目

Kubernetes之部署SpringBoot项目创建一个SpringBoot项目将SpringBoot项目打成Jar包使用Dockerfile制作镜像部署SpringBoot项目创建一个SpringBoot项目 pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache…...

vscode在远程服务器提交git的时候无需每次都要输入账号密码的配置

要避免在每次 git 操作时都需要输入账号和密码&#xff0c;可以使用 SSH 鉴权&#xff0c;具体步骤如下&#xff1a;生成 SSH key在本地计算机上使用命令 ssh-keygen -t rsa -b 4096 生成 SSH key。这个命令将在 ~/.ssh 目录下生成两个文件&#xff1a;id_rsa 和 id_rsa.pub&am…...

【Spring 基础】

【Spring 基础】 一、 Spring 介绍 1. 简述 Spring 技术是 JavaEE 开发必备技能&#xff0c;企业开发技术选型专业角度 简化开发&#xff0c;降低企业级开发的复杂性 IoCAOP 事务处理 框架整合&#xff0c;高效整合其他技术&#xff0c;提高企业级应用开发与运行效率 MyBat…...

2023年全国最新机动车签字授权人精选真题及答案5

百分百题库提供机动车签字授权人考试试题、机动车签字授权人考试预测题、机动车签字授权人考试真题、机动车签字授权人证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 四、多选题 1.以下哪些气体属于排放污染物&#xff08…...

5138: 数字游戏

描述爸爸、妈妈还有YuYu一起玩一个数字游戏&#xff0c;玩家从某个数开始挨个轮流报数&#xff0c;当数字里含有4或7时&#xff0c;不能报出该数字&#xff0c;只能拍一下手。报数的顺序总是从YuYu开始&#xff0c;然后妈妈、爸爸&#xff0c;最后回到YuYu&#xff0c;以此类推…...

阅读笔记9——DenseNet

一、DenseNet DenseNet的网络结构如图1-1所示&#xff0c;其核心是Dense Block模块&#xff0c;Dense Block中的一个黑点就代表一个卷积模块&#xff08;不是一个卷积层&#xff0c;而是DenseNet提出的一个BottleNeck模块&#xff0c;后文有讲解&#xff09;&#xff0c;每条黑…...

PowerAutomation获取邮件附件并删除这个邮件方法

这个文章是怎么来的呢&#xff1f;现在不是低代码开发平台启蒙阶段嘛&#xff1f;笔者也有幸在工作中进行了尝试&#xff0c;目前也已经在实际工作中结合Python进行了使用&#xff0c;当然&#xff0c;是可以提高IT的工作效率的。需求是这样的&#xff0c;想从公司的EBS平台报表…...

websocket报错集锦-不断更新中

问题1&#xff1a;Failed to construct ‘WebSocket’: An insecure WebSocket connection may not be initiated from a page loaded over HTTPS. 问题描述 Mixed Content: The page at https://AAAAAA.com was loaded over HTTPS, but attempted to connect to the insecur…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...