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

(十二)排序算法-插入排序

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 概述 插入排序属于内部排序法&#xff0c;是对于欲排序的元素以插入的方式找寻该元素的适当位置&#xff0c;以达到排序的目的。 插入排序的工作方式非常像人们排序一手扑克牌一样。开始时&#xff0c;我们的左手为空并且桌子上的牌面朝下。然后&#xff0c;…...

elasticsearch 认知

1.大数据领域需要解决以下三个问题 如何存储数据 传统的关系数据库&#xff08;MySQL、Oracle、和Access等&#xff09;主导了20世纪的数据存储模式&#xff0c;但当数据量达到太字节级&#xff0c;甚至拍字节级时&#xff0c;关系型数据库表现出了难以解决的瓶颈问题。为了解决…...

《人体地图》笔记

《人体地图》 坂井建雄 著 孙浩 译 腹部通向大腿的隧道 腹部与大腿的分界点是大腿根部&#xff0c;即是腹股沟。 腹壁肌肉连结在腹股沟韧带上&#xff0c;腹壁肌肉包括三层&#xff0c;分别为腹外斜肌、腹内斜肌和腹横肌&#xff0c;每块肌肉都有一个张开的小孔&#xff0c;…...

java基础集合面试题

什么是集合 集合就是一个放数据的容器&#xff0c;准确的说是放数据对象引用的容器 集合类存放的都是对象的引用&#xff0c;而不是对象的本身 集合类型主要有3种&#xff1a;set(集&#xff09;、list(列表&#xff09;和map(映射)。 集合的特点 集合的特点主要有如下两点&…...

Vue学习-Vue入门

Vue学习 一、Vue入门 1、 引入Vue Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与第三方库…...

【项目】bxg基于SaaS的餐掌柜项目实战(2023)

基于SaaS的餐掌柜项目实战 餐掌柜是一款基于SaaS思想打造的餐饮系统&#xff0c;采用分布式系统架构进行多服务研发&#xff0c;共包含4个子系统&#xff0c;分别为平台运营端、管家端&#xff08;门店&#xff09;、收银端、小程序端&#xff0c;为餐饮商家打造一站式餐饮服务…...

灌区流量监测设备-中小灌区节水改造

系统概述 灌区信息化管理系统主要对对灌区的水情、雨情、土壤墒情、气象等信息进行监测&#xff0c;对重点区域进行视频监控&#xff0c;同时对泵站、闸门进行远程控制&#xff0c;实现了信息的测量、统计、分析、控制、调度等功能。为灌区管理部门科学决策提供了依据&#xf…...

SpringBoot2核心功能 --- 指标监控

一、SpringBoot Actuator 1.1、简介 未来每一个微服务在云上部署以后&#xff0c;我们都需要对其进行监控、追踪、审计、控制等。SpringBoot就抽取了Actuator场景&#xff0c;使得我们每个微服务快速引用即可获得生产级别的应用监控、审计等功能。 <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论文翻译

摘要 在电子商务行业&#xff0c;利用丰富的历史行为数据更好地提取用户兴趣对于构建在线广告系统的点击率(CTR)预测模型至关重要。关于用户行为数据有两个关键观察结果&#xff1a;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左右音质最好的蓝牙耳机

无线耳机是人们日常生活中必不可少的设备&#xff0c;无论是听音乐化石看电影都能获得身临其境的感觉&#xff0c;由于科技真在发展中&#xff0c;不断地的发生变化&#xff0c;百元价位就可以感受到不错的音色&#xff0c;下面小编整理了几款300左右音质表现不错的蓝牙耳机。 …...

【消息队列】聊一下生产者消息发送流程

消息发送流程 1.生产者main线程调用send发送消息&#xff0c;先走拦截器&#xff0c;然后会将消息进行序列化&#xff0c;然后选择对应的分区器&#xff0c;将消息发送到RecordAccumulator中&#xff0c;默认是32m 2.Sender线程会异步读取&#xff0c;要不数据达到batch的大小 …...

特斯拉和OpenAI的加持,马斯克简直人生赢家

赢家已定 商人行事&#xff0c;最重要的因素之一是利益驱动。这里&#xff0c;最服“马斯克”。 以马斯克为首的特斯拉公司周日宣布&#xff0c;将在上海新建一家超级工厂&#xff0c;专门生产该公司的储能产品Megapack。签约的特斯拉储能超级工厂项目也是该公司在美国本土以…...

优维低代码:第三方接口接入

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 连载…...

SQL 177. 第N高的薪水

SQL 177. 第N高的薪水数据需求解决方法1方法2题目 &#xff1a; 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天&#xff1a;交互式问答数字人发展现状 从一个真实案例开始&#xff0c;介绍当前主流的交互式数字人平台&#xff0c;需求和应用场景&#xff0c;引入交互式数字人的交互流程和关键技术。后续整个直播系列的内容安排。 第02天&#xff1a;音…...

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&#xff0c;以及该学生在 score 表中对应的 c_no 和 degree 。 SELECT no, name FROM student; ---------------- | no | name | ---------------- | 101 | 曾华 | | 102 | 匡明 | | 103 | 王丽 | | 104 | 李军 | | 105 | 王芳…...

「Bug」OpenCV读取图像为 None 分析

头一次遇到 OpenCV 无法读取图像&#xff0c;并且没有任何提示&#xff0c;首先怀疑的就是中文路径&#xff0c;因为大概率是这个地方出错的&#xff0c;但是修改完依旧是None&#xff0c;这就很苦恼了&#xff0c;分析了下出现None的原因&#xff0c;大概有以下三种情况&#…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题

20250609在荣品的PRO-RK3566开发板的Android13下解决串口可以执行命令但是脚本执行命令异常的问题 2025/6/9 20:54 缘起&#xff0c;为了跨网段推流&#xff0c;千辛万苦配置好了网络参数。 但是命令iptables -t filter -F tetherctrl_FORWARD可以在调试串口/DEBUG口正确执行。…...