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

算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

1. 插入排序(insertion-sort):

                                          是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

    算法稳定性:

                        对于两个相同的数,经过排序后,他们依旧保持之前的顺序,二者次序没有发生变化。插入排序是算法稳定的

   时间复杂度

        最优情况

                      在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为O(n)

        最坏情况

                          最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(n_{}^{2}

     动态图

  递归代码:

package com.nami.algorithm.study.day06;import java.util.Arrays;/*** beyond u self and trust u self.** @Author: lbc* @Date: 2023-09-05 15:36* @email: 594599620@qq.com* @Description: keep coding*/
public class InsertionSort {/*** 插入排序:* 从右向左找** @param target*/public static void sort(int[] target) {insertion(target, 1);}/*** 递归 缩小结果集** @param target* @param lowIndex*/private static void insertion(int[] target, int lowIndex) {if (lowIndex == target.length) {return;}int t = target[lowIndex];// 已排序区域指针int i = lowIndex - 1;// 没有找到插入位置while (i >= 0 && target[i] > t) {target[i + 1] = target[i];i--;// 如果到达数组0时候 依旧没有找到,则退出循环// 抽出,合并到while内
//            if(i < 0) {
//                break;
//            }}//插入位置找到了// 优化减少不必要的赋值动作,// 需要替换的数组值,正好是大于i, i+1索引的值不需要动,这个赋值动作就不必要了if (i + 1 != lowIndex) {target[i + 1] = t;}insertion(target, lowIndex + 1);}/*** 两种写法,这种赋值次数更多* 时间复杂度相同* 但是 效率没有上面的高,消耗在更多的赋值操作上了** @param target* @param lowIndex*/private static void insertion0(int[] target, int lowIndex) {if (lowIndex == target.length) {return;}// 已排序区域指针int i = lowIndex - 1;// 没有找到插入位置while (i >= 0 && target[i] > target[i + 1]) {int temp = target[i];target[i] = target[i + 1];target[i + 1] = temp;i--;}insertion(target, lowIndex + 1);}public static void main(String[] args) {int[] test = new int[]{1, 54, 234, 675, 32432, 23, 78, 459, 354, 9, 344, 22, 46, 85, 236, 3278, 245, 83, 154, 2, 1, 34, 73, 23};int[] test2 = new int[]{2, 4, 7, 3, 2, 1};
//        sort(test, test.length);sort(test);System.out.println(Arrays.toString(test));}}

相关文章:

算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

1. 插入排序&#xff08;insertion-sort&#xff09;&#xff1a; 是一种简单直观的排序算法。它的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入 算法稳定性: 对于两个相同的数&#xff0c;经过…...

OpenCV(二十二):均值滤波、方框滤波和高斯滤波

目录 1.均值滤波 2.方框滤波 3.高斯滤波 1.均值滤波 OpenCV中的均值滤波&#xff08;Mean Filter&#xff09;是一种简单的滤波技术&#xff0c;用于平滑图像并减少噪声。它的原理非常简单&#xff1a;对于每个像素&#xff0c;将其与其周围邻域内像素的平均值作为新的像素值…...

二叉树的递归遍历和非递归遍历

目录 一.二叉树的递归遍历 1.先序遍历二叉树 2.中序遍历二叉树 3.后序遍历二叉树 二.非递归遍历(栈) 1.先序遍历 2.中序遍历 3.后序遍历 一.二叉树的递归遍历 定义二叉树 #其中TElemType可以是int或者是char,根据要求自定 typedef struct BiNode{TElemType data;stru…...

JDK17:未来已来,你准备好了吗?

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

K8s和Docker

Kubernetes&#xff08;简称为K8s&#xff09;和Docker是两个相关但又不同的技术。 一、Docker 1、Docker是一种容器化平台&#xff0c;用于将应用程序及其依赖项打包成可移植的容器。 2、Docker容器可以在任何支持Docker的操作系统上运行 好处&#xff1a;提供了一种轻量级…...

使用物理机服务器应该注意的事项

使用物理机服务器应该注意的事项 如今云计算的发展已经遍布各大领域&#xff0c;尽管现在的云服务器火遍全网&#xff0c;但是仍有一些大型企业依旧选择使用独立物理服务器&#xff0c;你知道这是为什么吗&#xff1f;壹基比小鑫来告诉你吧。 独立物理服务器托管业务适合大中…...

py脚本解决ArcGIS Server服务内存过大的问题

在一台服务器上&#xff0c;使用ArcGIS Server发布地图服务&#xff0c;但是地图服务较多&#xff0c;在发布之后&#xff0c;服务器的内存持续处在95%上下的高位状态&#xff0c;导致服务器运行状态不稳定&#xff0c;经常需要重新启动。重新启动后重新进入这种内存高位的陷阱…...

Go语言Web开发入门指南

Go语言Web开发入门指南 欢迎来到Go语言的Web开发入门指南。Go语言因其出色的性能和并发支持而成为Web开发的热门选择。在本篇文章中&#xff0c;我们将介绍如何使用Go语言构建简单的Web应用程序&#xff0c;包括路由、模板、数据库连接和静态文件服务。 准备工作 在开始之前…...

保姆级教程——VSCode如何在Mac上配置C++的运行环境

vscode官方下载&#xff1a; 点击官网链接&#xff0c;下载对应的pkg&#xff0c;安装打开&#xff1b; https://code.visualstudio.com/插件安装 点击箭头所指插件商店按钮&#xff0c;yyds&#xff1b; 下载C/C 插件&#xff1b; ![外链图片转存 下载CodeLLDB插件&#x…...

Java 操作FTP服务器进行下载文件

用Java去操作FTP服务器去做下载&#xff0c;本文章里面分为单个下载和批量下载&#xff0c;批量下载只不过多了一层循环&#xff0c;为了方便参考&#xff0c;我代码都贴出来了。 不管单个下载还是多个&#xff0c;一定要记得&#xff0c;远程服务器的直接写文件夹路径&#xf…...

物理机服务器应该注意的事

物理机服务器应该注意的事 1、选址 服务器是个非常重要的硬件产品&#xff0c;对机房的也是有一定的要求的&#xff0c;比如温度、安全性&#xff0c;噪音、电源稳定性等等问题都需要解决!但是不是每个人都会选择自己建立一个机房&#xff0c;毕竟各方面加起来的成本都太高。这…...

信息化发展24

信息技术的发展 1 &#xff09;在计算机软硬件方面&#xff0c; 计算机硬件技术将向超高速、超小型、平行处理、智能化的方向发展&#xff0c; 计算机硬件设备的体积越来越小、速度越来越高、容量越来越大、功耗越来越低、可靠性越来越高。 2 &#xff09;计算机软件越来越丰富…...

Qt开发_调用OpenCV(3.4.7)设计完成人脸检测系统

一、前言 近年来,人脸识别技术得到了广泛的应用,它可以在各种场景中实现自动化的人脸检测和识别,例如安防监控、人脸解锁、人脸支付等。 该项目的目标是设计一个简单易用但功能强大的人脸检测系统,可以实时从摄像头采集视频,并对视频中的人脸进行准确的检测和框选。通过…...

Java 中 List 删除元素

fori循环 删除某个元素后&#xff0c;list的大小发生了变化&#xff0c;会导致遍历准确。 这种方式可以用在删除特定的一个元素时使用&#xff0c;但不适合循环删除多个元素时使用 增强for循环 删除元素后继续循环会报错误信息ConcurrentModificationException&#xff0c;但是…...

Redis:StringRedisTemplate简介

&#xff08;笔记总结自b站黑马程序员课程&#xff09; 为了在反序列化时知道对象的类型&#xff0c;JSON序列化器会将类的class类型写入json结果中&#xff0c;存入Redis&#xff0c;会带来额外的内存开销。 为了减少内存的消耗&#xff0c;我们可以采用手动序列化的方式&am…...

pytorch-神经网络-手写数字分类任务

Mnist分类任务&#xff1a; 网络基本构建与训练方法&#xff0c;常用函数解析 torch.nn.functional模块 nn.Module模块 读取Mnist数据集 会自动进行下载 %matplotlib inlinefrom pathlib import Path import requestsDATA_PATH Path("data") PATH DATA_PATH / &…...

【群智能算法改进】一种改进的鹈鹕优化算法 IPOA算法[1]【Matlab代码#57】

文章目录 【获取资源请见文章第5节&#xff1a;资源获取】1. 原始POA算法2. 改进后的IPOA算法2.1 Sine映射种群初始化2.2 融合改进的正余弦策略2.3 Levy飞行策略 3. 部分代码展示4. 仿真结果展示5. 资源获取 【获取资源请见文章第5节&#xff1a;资源获取】 1. 原始POA算法 此…...

C++初阶:C++入门

目录 一.iostream文件 二.命名空间 2.1.命名空间的定义 2.2.命名空间的使用 三.C的输入输出 四.缺省参数 4.1.缺省参数概念 4.2.缺省参数分类 4.3.缺省参数注意事项 4.4.缺省参数用途 五.函数重载 5.1.重载函数概念 5.2.C支持函数重载的原理--名字修饰(name Mangl…...

golang操作数据库--gorm框架、redis

目录 1.数据库相关操作(1)非orm框架①引入②初始化③增删改查 (2) io版orm框架 (推荐用这个)①引入②初始化③增删改查④gorm gen的使用 (3) jinzhu版orm框架①引入②初始化③增删改查 2.redis(1)引入(2)初始化①普通初始化②v8初始化③get/set示例 1.数据库相关操作 (1)非orm…...

10 种常用的字符串方法

10 种常用的字符串方法 1.concat() 字符串拼接 const str1 12345678;const str2 abcdefgh;const str3 -【】&#xff1b;‘;console.log(str1.concat(str2,str3))//12345678abcdefgh-【】&#xff1b;‘ 2.includes() 判断字符串中是否包含指定值&#xff0c;返回布尔值…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...