数据结构-插入排序实现
文章目录
- 1、描述
- 2、代码实现
- 3、结果
- 4、复杂度
1、描述
待排序的数组分为已排序、未排序两部分;
初始状态时,仅有第一个元素为已排序序列,第一个以外的元素为未排序序列;
此后遍历未排序序列, 将元素逐一插入到已排序的序列中:即把该为排序元素与原有一排序序列当做一个新序列,通过一次冒泡排序整合成已排序序列(从右侧开始,两个相邻元素进行比较,匹配成功则换位置,不成功就不做变动)
例:
| 源数据 | 3 | 2 | 1 |
|---|---|---|---|
| 步骤1 (3为已排序,2、1 为未排序;3 和 2 比较) | 2 | 3 | 1 |
| 步骤2.1 (2、3为已排序,1为未排序;3 和 1 比较) | 2 | 1 | 3 |
| 步骤2.2 (2 和 1 比较) | 1 | 2 | 3 |
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、描述 待排序的数组分为已排序、未排序两部分; 初始状态时,仅有第一个元素为已排序序列,第一个以外的元素为未排序序列; 此后遍历未排序序列, 将元素逐一插入到已排序的序列中&am…...
CGlib动态代理和JDK动态代理
CGlib代理模式是一种基于字节码操作的代理模式,它通过生成被代理类的子类来实现代理功能。 CGlib通过继承被代理类,生成一个代理类的子类,并重写父类的方法,在方法的前后插入相应的代理逻辑。这种方式不需要被代理类实现接口&…...
分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测
分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测 目录 分类预测 | Matlab实现PSO-GRU-Attention粒子群算法优化门控循环单元融合注意力机制多特征分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现PSO…...
Python OpenCV 视频抽帧处理并保存
上篇文章中基于OpenCV实现图像处理后,类似的,也可以对视频进行处理。OpenCV库可以将视频的每一帧读取出来,然后对每一帧图像做相应的操作,并保存成新的视频。 1. 读取视频,获取相关参数 import cv2 import numpy as…...
英伟达AI布局的新动向:H200 GPU开启生成式AI的新纪元
英伟达Nvidia是全球领先的AI计算平台和GPU制造商,近年来一直在不断推出创新的AI产品和解决方案,为各行各业的AI应用提供强大的支持。 最近,英伟达在GTC 2023大会上发布了一款专为训练和部署生成式AI模型的图形处理单元(GPU&#…...
Windows11 python3.12 安装pyqt6 pyqt6-tools
Windows11 python3.12 安装pyqt6比较容易,但pyqt6-tools一直安装不上去。出错信息如下: (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(reverse shell)就是控制端监听在某TCP/UDP端口,被控端发起请求到该端口,并将其命令行的输入输出转到控制端。reverse shell与telnet,ssh等标准shell对应,本质上是网络概念的客户端与服务端…...
Guava RateLimiter的限流机制详解
限流是保护高并发系统的三种有效方法之一。另外两个分别是缓存和降级。限流在很多场景中都会使用到限制并发数和请求数。例如,在限时抢购的情况下,限流可以保护您自己的系统和下游系统不被巨大的流量淹没。 限流的目的是通过限制并发访问或请求或者限制…...
详解nginx的root与alias
在Nginx中,root和alias指令都可以用来指定Web服务器中的文件根目录。不过,它们之间有一些关键的区别。 root指令指定的是服务器根目录,是用于处理HTTP请求时所使用的默认根目录。例如,若root /var/www/html;,则访问htt…...
在HBuilderX中配置Vue Router的步骤
以下是在HBuilderX中配置Vue Router的步骤: 在项目中安装Vue Router,可以使用npm或yarn命令进行安装。 在src目录下创建routers.js文件,并在该文件中编写路由相关代码,例如: import Vue from vue import Router from …...
通过接口抓取公众号信息并群发
总体步骤 通过非官方接口,登陆公众号获取cookie、token通过token拼接需要的参数,请求被抓取的公众号列表数据通过列表数据获取文章内容解析文章内容并通过官方接口创建草稿通过非官方接口群发创建的草稿(非认证用户,已认证用户可以通过官方接…...
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 及更高版本(内部版本 19041 及更高版本)或 Windows 11 才能使用以下命令 在设置,系统里面就能看到 开启windows功能 直接winQ搜 开启hyber-V、使用于Linux的Windows子系统、虚拟机平…...
音视频项目—基于FFmpeg和SDL的音视频播放器解析(十二)
介绍 在本系列,我打算花大篇幅讲解我的 gitee 项目音视频播放器,在这个项目,您可以学到音视频解封装,解码,SDL渲染相关的知识。您对源代码感兴趣的话,请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...
键鼠自动化2.0树形结构讲解
介绍 在键鼠自动化2.0中使用Qtc实现了全自定义树形结构,实现任务的拖拽,复制粘贴,撤销重做,以及包括树形结构增加序号展示,以及增加搜索功能 实现 1.自定义节点 // 自定义节点类 class TreeNode : public QObject …...
2023年【金属非金属矿山安全检查(地下矿山)】考试报名及金属非金属矿山安全检查(地下矿山)最新解析
题库来源:安全生产模拟考试一点通公众号小程序 金属非金属矿山安全检查(地下矿山)考试报名参考答案及金属非金属矿山安全检查(地下矿山)考试试题解析是安全生产模拟考试一点通题库老师及金属非金属矿山安全检查&#…...
Java 12 及Tomcat 部署配置
使用的软件版本 1. Java12部署 和之前的Java版本不太一样,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(日期范围,频度,和位移)1 Generating Date Ranges(生成日期范围)2 Frequencies and Date Offsets(频度和日期偏移)Week of mo…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
