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

数据结构-插入排序实现

文章目录

        • 1、描述
        • 2、代码实现
        • 3、结果
        • 4、复杂度

1、描述
待排序的数组分为已排序、未排序两部分;
初始状态时,仅有第一个元素为已排序序列,第一个以外的元素为未排序序列;
此后遍历未排序序列, 将元素逐一插入到已排序的序列中:即把该为排序元素与原有一排序序列当做一个新序列,通过一次冒泡排序整合成已排序序列(从右侧开始,两个相邻元素进行比较,匹配成功则换位置,不成功就不做变动)

例:

源数据321
步骤1 (3为已排序,2、1 为未排序;3 和 2 比较)231
步骤2.1 (2、3为已排序,1为未排序;3 和 1 比较)213
步骤2.2 (2 和 1 比较)123
2、代码实现
public class SimpleInsertSort {// 数组长度public final static int MAX_SIZE = 10;// 复杂度public static long complexity = 0;// 打印public static void print(Object[] params) {System.out.println(Arrays.toString(params));}public static void main(String[] args) {Integer[] arr = new Integer[MAX_SIZE];// 数组填充数据for (int i = 0; i < arr.length; i++) {arr[i] = Integer.valueOf(Math.round(Math.random() * 100) + "");}System.out.printf("数据:");print(arr);// 第 i 位置数据和前置数据作比较for (int i = 1; i < arr.length; i++) {int temp = arr[i];// 进入循环前0-(i-1)范围的数据已经是排序数据;跳出后表示0-i已排序// < temp: 降序 ; > temp: 升序// 该循环相当于冒泡排序(局部)for (int j = i; j > 0 && arr[j-1] > temp; j--) {complexity++;arr[j] = arr[j-1];arr[j-1] = temp;}}System.out.printf("结果:");print(arr);System.out.println("复杂度:" + complexity);}
}
3、结果
数据:[12, 18, 75, 25, 71, 59, 84, 42, 87, 13]
结果:[12, 13, 18, 25, 42, 59, 71, 75, 84, 87]
复杂度:16
4、复杂度
最好情况,第二个循环都不需要执行,O(N)
最坏情况,第一个以外的元素都需要和之前的数据做一次交换 O(N*N)

相关文章:

数据结构-插入排序实现

文章目录 1、描述2、代码实现3、结果4、复杂度 1、描述 待排序的数组分为已排序、未排序两部分; 初始状态时&#xff0c;仅有第一个元素为已排序序列&#xff0c;第一个以外的元素为未排序序列&#xff1b; 此后遍历未排序序列&#xff0c; 将元素逐一插入到已排序的序列中&am…...

CGlib动态代理和JDK动态代理

CGlib代理模式是一种基于字节码操作的代理模式&#xff0c;它通过生成被代理类的子类来实现代理功能。 CGlib通过继承被代理类&#xff0c;生成一个代理类的子类&#xff0c;并重写父类的方法&#xff0c;在方法的前后插入相应的代理逻辑。这种方式不需要被代理类实现接口&…...

分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测

分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测 目录 分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现PSO…...

Python OpenCV 视频抽帧处理并保存

上篇文章中基于OpenCV实现图像处理后&#xff0c;类似的&#xff0c;也可以对视频进行处理。OpenCV库可以将视频的每一帧读取出来&#xff0c;然后对每一帧图像做相应的操作&#xff0c;并保存成新的视频。 1. 读取视频&#xff0c;获取相关参数 import cv2 import numpy as…...

英伟达AI布局的新动向:H200 GPU开启生成式AI的新纪元

英伟达Nvidia是全球领先的AI计算平台和GPU制造商&#xff0c;近年来一直在不断推出创新的AI产品和解决方案&#xff0c;为各行各业的AI应用提供强大的支持。 最近&#xff0c;英伟达在GTC 2023大会上发布了一款专为训练和部署生成式AI模型的图形处理单元&#xff08;GPU&#…...

Windows11 python3.12 安装pyqt6 pyqt6-tools

Windows11 python3.12 安装pyqt6比较容易&#xff0c;但pyqt6-tools一直安装不上去。出错信息如下&#xff1a; (venv) PS D:\python_project\pyqt6> pip install pyqt6-tools Collecting pyqt6-toolsUsing cached pyqt6_tools-6.4.2.3.3-py3-none-any.whl (29 kB) Collec…...

反弹Shell

概述 反弹shell&#xff08;reverse shell&#xff09;就是控制端监听在某TCP/UDP端口&#xff0c;被控端发起请求到该端口&#xff0c;并将其命令行的输入输出转到控制端。reverse shell与telnet&#xff0c;ssh等标准shell对应&#xff0c;本质上是网络概念的客户端与服务端…...

Guava RateLimiter的限流机制详解

限流是保护高并发系统的三种有效方法之一。另外两个分别是缓存和降级。限流在很多场景中都会使用到限制并发数和请求数。例如&#xff0c;在限时抢购的情况下&#xff0c;限流可以保护您自己的系统和下游系统不被巨大的流量淹没。 限流的目的是通过限制并发访问或请求或者限制…...

详解nginx的root与alias

在Nginx中&#xff0c;root和alias指令都可以用来指定Web服务器中的文件根目录。不过&#xff0c;它们之间有一些关键的区别。 root指令指定的是服务器根目录&#xff0c;是用于处理HTTP请求时所使用的默认根目录。例如&#xff0c;若root /var/www/html;&#xff0c;则访问htt…...

在HBuilderX中配置Vue Router的步骤

以下是在HBuilderX中配置Vue Router的步骤&#xff1a; 在项目中安装Vue Router&#xff0c;可以使用npm或yarn命令进行安装。 在src目录下创建routers.js文件&#xff0c;并在该文件中编写路由相关代码&#xff0c;例如&#xff1a; import Vue from vue import Router from …...

通过接口抓取公众号信息并群发

总体步骤 通过非官方接口&#xff0c;登陆公众号获取cookie、token通过token拼接需要的参数&#xff0c;请求被抓取的公众号列表数据通过列表数据获取文章内容解析文章内容并通过官方接口创建草稿通过非官方接口群发创建的草稿(非认证用户&#xff0c;已认证用户可以通过官方接…...

Python基础入门----如何通过conda搭建Python开发环境

文章目录 使用 conda 搭建Python开发环境是非常方便的,它可以帮助你管理Python版本、依赖库、虚拟环境等。以下是一个简单的步骤,演示如何通过 conda 搭建Python开发环境: 安装conda: 如果你还没有安装 conda,首先需要安装Anaconda或Miniconda。Anaconda是一个包含很多数据…...

计算机网络的体系结构

目录 一. 计算机体系结构的形成二. 协议与层次划分2.1 数据传输过程2.2 什么是网络协议2.3 网络协议的三要素2.4 协议有两种形式2.4 各层协议2.5 什么是复用和分用 \quad 一. 计算机体系结构的形成 \quad 计算机网络是一个非常复杂的系统, 相互通信的两个计算机系统必须高度协调…...

cesium雷达扫描(模糊圆效果)

cesium雷达扫描(模糊圆效果) 1、实现思路 使用ellipse方法加载圆型,修改ellipse中‘material’方法重写自己的glsl来实现当前效果 1、示例源码 index.html <!DOCTYPE html> <html lang="en"><head><!<...

windows安装wsl2以及ubuntu

查看自己系统的版本 必须运行 Windows 10 版本 2004 及更高版本&#xff08;内部版本 19041 及更高版本&#xff09;或 Windows 11 才能使用以下命令 在设置&#xff0c;系统里面就能看到 开启windows功能 直接winQ搜 开启hyber-V、使用于Linux的Windows子系统、虚拟机平…...

音视频项目—基于FFmpeg和SDL的音视频播放器解析(十二)

介绍 在本系列&#xff0c;我打算花大篇幅讲解我的 gitee 项目音视频播放器&#xff0c;在这个项目&#xff0c;您可以学到音视频解封装&#xff0c;解码&#xff0c;SDL渲染相关的知识。您对源代码感兴趣的话&#xff0c;请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...

键鼠自动化2.0树形结构讲解

介绍 在键鼠自动化2.0中使用Qtc实现了全自定义树形结构&#xff0c;实现任务的拖拽&#xff0c;复制粘贴&#xff0c;撤销重做&#xff0c;以及包括树形结构增加序号展示&#xff0c;以及增加搜索功能 实现 1.自定义节点 // 自定义节点类 class TreeNode : public QObject …...

2023年【金属非金属矿山安全检查(地下矿山)】考试报名及金属非金属矿山安全检查(地下矿山)最新解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 金属非金属矿山安全检查&#xff08;地下矿山&#xff09;考试报名参考答案及金属非金属矿山安全检查&#xff08;地下矿山&#xff09;考试试题解析是安全生产模拟考试一点通题库老师及金属非金属矿山安全检查&#…...

Java 12 及Tomcat 部署配置

使用的软件版本 1. Java12部署 和之前的Java版本不太一样&#xff0c;12版本不用配置JRE环境。 解压缩文件夹 root账户执行 tar -xzvf /home/software/jdk-12.0.2_linux-x64_bin.tar.gz创建java文件夹 root账户执行 cd /usr mkdir java移动Java文件到创建的文件夹下 root账…...

pandas教程:Date Ranges, Frequencies, and Shifting 日期范围,频度,和位移

文章目录 11.3 Date Ranges, Frequencies, and Shifting&#xff08;日期范围&#xff0c;频度&#xff0c;和位移&#xff09;1 Generating Date Ranges&#xff08;生成日期范围&#xff09;2 Frequencies and Date Offsets&#xff08;频度和日期偏移&#xff09;Week of mo…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

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

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

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...