(十二)排序算法-插入排序
1 基本介绍
1.1 概述
插入排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。
插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,我
们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在
手中的每张牌进行比较,如下图所示:

它的算法思想则是将整个序列划分成两段,一段时已经排序完成的序列,另一端序列则是仍然无需的状态,下图所示。

分成这样两个序列之后,插入序列每次都是挑选待排序序列的队头元素插入到已有序的序列之中,从有序序列的队尾开始比较,如果比该元素大的话,将该元素后移,一旦出现小于该元素的元素,插入当前的位置。这个就是插入排序名字的由来。
1.2 算法详解
插入排序大思想:
插入排序(Insertion Sorting)的基本思想是:把 n 个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有 n-1 个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
插入排序思路图,如下所示。

动画展示:

2 代码实现
2.1 代码实现
/*** 插入排序*/
public class InsertSort {public static void main(String[] args) {int[] arr = {45,2,6,265,2,5,74,52};System.out.println(Arrays.toString(arr));System.out.println("------------排序前------------");insertSort(arr);System.out.println("------------排序后------------");System.out.println(Arrays.toString(arr));}// 插入排序public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int insertVal = arr[i];int insertIndex = i - 1;while (insertIndex >= 0 && insertVal < arr[insertIndex]) {arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}arr[insertIndex+1] = insertVal;System.out.println("第" + i + "轮插入");System.out.println(Arrays.toString(arr));}}
}
3 复杂度分析
时间复杂度
最坏情况:当待排序序列为逆序状态,首先遍历整个序列,之后一个一个地将待插入元素放在已排好序的序列最前面,之后的所有元素都需要向后移动一位,时间复杂度为O(n^2)
最好情况:当待排序序列为正序状态,则遍历完整个序列,当插入元素时,只比较一次就够了,所以时间复杂度为O(n)
平均情况:当被插入的元素放在已排序的序列中间位置时,为平均情况,比较和移动的时间复杂度为O(n/2),所以总的时间复杂度依然为O(n^2)
空间复杂度
空间复杂度为O(1)
稳定性
当待插入元素与有序序列中比较的元素相等时,将待插入元素直接插入在该相等元素的后面。所以,两个元素位置的前后顺序没有改变,故插入排序是稳定的
相关文章:
(十二)排序算法-插入排序
1 基本介绍 1.1 概述 插入排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。 插入排序的工作方式非常像人们排序一手扑克牌一样。开始时,我们的左手为空并且桌子上的牌面朝下。然后,…...
elasticsearch 认知
1.大数据领域需要解决以下三个问题 如何存储数据 传统的关系数据库(MySQL、Oracle、和Access等)主导了20世纪的数据存储模式,但当数据量达到太字节级,甚至拍字节级时,关系型数据库表现出了难以解决的瓶颈问题。为了解决…...
《人体地图》笔记
《人体地图》 坂井建雄 著 孙浩 译 腹部通向大腿的隧道 腹部与大腿的分界点是大腿根部,即是腹股沟。 腹壁肌肉连结在腹股沟韧带上,腹壁肌肉包括三层,分别为腹外斜肌、腹内斜肌和腹横肌,每块肌肉都有一个张开的小孔,…...
java基础集合面试题
什么是集合 集合就是一个放数据的容器,准确的说是放数据对象引用的容器 集合类存放的都是对象的引用,而不是对象的本身 集合类型主要有3种:set(集)、list(列表)和map(映射)。 集合的特点 集合的特点主要有如下两点&…...
Vue学习-Vue入门
Vue学习 一、Vue入门 1、 引入Vue Vue (读音 /vjuː/,类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是,Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层,不仅易于上手,还便于与第三方库…...
【项目】bxg基于SaaS的餐掌柜项目实战(2023)
基于SaaS的餐掌柜项目实战 餐掌柜是一款基于SaaS思想打造的餐饮系统,采用分布式系统架构进行多服务研发,共包含4个子系统,分别为平台运营端、管家端(门店)、收银端、小程序端,为餐饮商家打造一站式餐饮服务…...
灌区流量监测设备-中小灌区节水改造
系统概述 灌区信息化管理系统主要对对灌区的水情、雨情、土壤墒情、气象等信息进行监测,对重点区域进行视频监控,同时对泵站、闸门进行远程控制,实现了信息的测量、统计、分析、控制、调度等功能。为灌区管理部门科学决策提供了依据…...
SpringBoot2核心功能 --- 指标监控
一、SpringBoot Actuator 1.1、简介 未来每一个微服务在云上部署以后,我们都需要对其进行监控、追踪、审计、控制等。SpringBoot就抽取了Actuator场景,使得我们每个微服务快速引用即可获得生产级别的应用监控、审计等功能。 <dependency><gro…...
python实战应用讲解-【numpy数组篇】常用函数(三)(附python示例代码)
目录 Python numpy.repeat() Python numpy.tile() Python numpy.asarray_chkfinite() Python numpy.asfarray() Python numpy.asfortranarray() Python numpy.repeat() Python numpy.repeat()函数重复数组中的元素 – arr. 语法 : numpy.repeat(arr, repetitions, axis …...
DIN论文翻译
摘要 在电子商务行业,利用丰富的历史行为数据更好地提取用户兴趣对于构建在线广告系统的点击率(CTR)预测模型至关重要。关于用户行为数据有两个关键观察结果:i) 多样性(diversity)。用户在访问电子商务网站时对不同种类的商品感兴趣。ii) 局部激活(local…...
python列表,元组和字典
1、python列表 1.1.列表的定义 list是一种有序的集合、基于 链表实现,name[ ] ,全局定义:list2list([ ])。 1.2下标索引 python不仅有负索引也有正索引。正索引从0开始,负索引从-1开始。这两个可以混用,但指向还是那个位置 a[0]a[-9]//length为10的数组a1.3列表的切片 列表可…...
300元左右的蓝牙耳机哪个好?300左右音质最好的蓝牙耳机
无线耳机是人们日常生活中必不可少的设备,无论是听音乐化石看电影都能获得身临其境的感觉,由于科技真在发展中,不断地的发生变化,百元价位就可以感受到不错的音色,下面小编整理了几款300左右音质表现不错的蓝牙耳机。 …...
【消息队列】聊一下生产者消息发送流程
消息发送流程 1.生产者main线程调用send发送消息,先走拦截器,然后会将消息进行序列化,然后选择对应的分区器,将消息发送到RecordAccumulator中,默认是32m 2.Sender线程会异步读取,要不数据达到batch的大小 …...
特斯拉和OpenAI的加持,马斯克简直人生赢家
赢家已定 商人行事,最重要的因素之一是利益驱动。这里,最服“马斯克”。 以马斯克为首的特斯拉公司周日宣布,将在上海新建一家超级工厂,专门生产该公司的储能产品Megapack。签约的特斯拉储能超级工厂项目也是该公司在美国本土以…...
优维低代码:第三方接口接入
优维低代码技术专栏,是一个全新的、技术为主的专栏,由优维技术委员会成员执笔,基于优维7年低代码技术研发及运维成果,主要介绍低代码相关的技术原理及架构逻辑,目的是给广大运维人提供一个技术交流与学习的平台。 连载…...
SQL 177. 第N高的薪水
SQL 177. 第N高的薪水数据需求解决方法1方法2题目 : https://leetcode.cn/problems/nth-highest-salary/ 数据 Create table If Not Exists Employee (Id int comment 主键列, Salary int comment 工资 );Truncate table Employee;insert into Employee (id, sala…...
14天手撸交互式问答数字人直播教程-课程计划
一、课程计划 二、时间安排 第01天:交互式问答数字人发展现状 从一个真实案例开始,介绍当前主流的交互式数字人平台,需求和应用场景,引入交互式数字人的交互流程和关键技术。后续整个直播系列的内容安排。 第02天:音…...
spring boot3.0新特性Http客户端远程调用
1、安装依赖 <!-- For reactive support --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-webflux</artifactId></dependency>2、项目结构 3、新建配置类WebConfig package com.exa…...
查询联系:多表查询 - 1
查询所有学生的 name,以及该学生在 score 表中对应的 c_no 和 degree 。 SELECT no, name FROM student; ---------------- | no | name | ---------------- | 101 | 曾华 | | 102 | 匡明 | | 103 | 王丽 | | 104 | 李军 | | 105 | 王芳…...
「Bug」OpenCV读取图像为 None 分析
头一次遇到 OpenCV 无法读取图像,并且没有任何提示,首先怀疑的就是中文路径,因为大概率是这个地方出错的,但是修改完依旧是None,这就很苦恼了,分析了下出现None的原因,大概有以下三种情况&#…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
uniapp 实现腾讯云IM群文件上传下载功能
UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中,群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS,在uniapp中实现: 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...
