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

排序算法之——直接插入排序

直接插入排序——以升序排列为例

  • 1.1基本思想
  • 1.2动态图示感知
  • 1.3静态图示详解
  • 1.4代码实现
  • 1.5时间复杂度
    • 1.5.1最好情况
    • 1.5.2最差情况
  • 1.6空间复杂度
  • 1.7稳定性
    • 1.7.1一个小问题

1.1基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。实际中我们玩扑克牌时,就用了插入排序的思想。
在这里插入图片描述

1.2动态图示感知

在这里插入图片描述

1.3静态图示详解

以一组待排序数据:5 3 1 6 9 9为例:
在这里插入图片描述

1.4代码实现

   public static void insertSort(int[] array){for(int i = 1;i < array.length;i++){int tmp = array[i];//初始化tmp的值int j = i - 1;for( ;j >= 0;j--){//这里带不带等号,会影响排序的稳定性if(array[j] > tmp){array[j+1] = array[j];}else{break;}}array[j + 1] = tmp;}}

1.5时间复杂度

1.5.1最好情况

当待排序数组已经是一个升序排列的数组时,此时时间复杂度最低。因为对于i遍历的每一个值,j无需向左遍历,此时只相当于i遍历了一遍数组(确切的说,是遍历了除第一个元素外的数组),因此时间复杂度为O(n)
在这里插入图片描述

1.5.2最差情况

当待排序数组已经是一个降序排列的数组时,此时时间复杂度最高。因为对于i遍历的每一个值,j需要向左遍历直到-1,因此整个排休的时间复杂度为O(n^2)
在这里插入图片描述
特点:由以上分析可知,待排序的数据越“有序”,直接插入排序算法的时间复杂度越低。这一特点可以用到某些排序算法的优化上,比如快速排序。

1.6空间复杂度

整个排序过程只创建了常数个临时变量,因此空间复杂度为O(1)

1.7稳定性

1.2图示详解中,原始数组中的数据9和9,在排序后相对位置没有发生变化,因此直接插入排序是稳定的排序

1.7.1一个小问题

如果将原有代码中的这句:

if(array[j] > tmp){array[j+1] = array[j];
}else{break;
}

改为:

if(array[j] >= tmp){array[j+1] = array[j];
}else{break;
}

即将判断条件的 “>” 改为 “>=”
原有的直接插入排序还是稳定的吗?
答:不稳定。

图示说明如下(对比1.3静态图示详解的最后两步):
在这里插入图片描述
所以直接插入排序是稳定的还是不稳定的呢?
前面已经说明了直接插入排序是稳定的排序。之所以会出现把 > 修改成 >=,原有的排序由稳定变为不稳定的情况,是因为:一个本身就不稳定的排序,是不可能是现成稳定的排序的;而一个本身稳定的排序,是可以实现为不稳定的排序的。

相关文章:

排序算法之——直接插入排序

直接插入排序——以升序排列为例 1.1基本思想1.2动态图示感知1.3静态图示详解1.4代码实现1.5时间复杂度1.5.1最好情况1.5.2最差情况 1.6空间复杂度1.7稳定性1.7.1一个小问题 1.1基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直…...

突出最强算法模型——回归算法 !!

文章目录 1、特征工程的重要性 2、缺失值和异常值的处理 &#xff08;1&#xff09;处理缺失值 &#xff08;2&#xff09;处理异常值 3、回归模型的诊断 &#xff08;1&#xff09;残差分析 &#xff08;2&#xff09;检查回归假设 &#xff08;3&#xff09;Cooks 距离 4、学…...

云数据库 Redis 性能深度评测(阿里云、华为云、腾讯云、百度智能云)

在当今的云服务市场中&#xff0c;阿里云、腾讯云、华为云和百度智能云都是领先的云服务提供商&#xff0c;他们都提供了全套的云数据库服务&#xff0c;其中 Redis属于RDS 之后第二被广泛应用的服务&#xff0c;本次测试旨在深入比较这四家云服务巨头在Redis云数据库性能方面的…...

Android---Retrofit实现网络请求:Java 版

简介 在 Android 开发中&#xff0c;网络请求是一个极为关键的部分。Retrofit 作为一个强大的网络请求库&#xff0c;能够简化开发流程&#xff0c;提供高效的网络请求能力。 Retrofit 是一个建立在 OkHttp 基础之上的网络请求库&#xff0c;能够将我们定义的 Java 接口转化为…...

使用静态CRLSP配置MPLS TE隧道

正文共&#xff1a;1591 字 13 图&#xff0c;预估阅读时间&#xff1a;4 分钟 静态CRLSP&#xff08;Constraint-based Routed Label Switched Paths&#xff0c;基于约束路由的LSP&#xff09;是指在报文经过的每一跳设备上&#xff08;包括Ingress、Transit和Egress&#xf…...

gentoo安装笔记

最近比较闲&#xff0c;所以挑战一下自己&#xff0c;在自己的台式电脑上安装gentoo 下面记录了我亲自安装的步骤&#xff0c;作为以后我再次安装时参考所用。 整体步骤 一般来将一个linux发行版的安装步骤其实大体上都差不多&#xff0c;基本分为一下几步&#xff1a; 1. …...

Git如何使用 五分钟快速入门

Git如何使用 五分钟快速入门 Git是一个分布式版本控制系统&#xff0c;它可以帮助开发人员跟踪和管理项目的代码变更。与传统的集中式版本控制系统&#xff08;如SVN&#xff09;不同&#xff0c;Git允许开发人员在本地存储完整的代码仓库&#xff0c;并且可以独立地进行代码修…...

FreeRTOS学习笔记——(FreeRTOS临界段代码保护及调度器挂起与恢复)

这里写目录标题 1&#xff0c;临界段代码保护简介&#xff08;熟悉&#xff09;2&#xff0c;临界段代码保护函数介绍&#xff08;掌握&#xff09;3&#xff0c;任务调度器的挂起和恢复&#xff08;熟悉&#xff09; 1&#xff0c;临界段代码保护简介&#xff08;熟悉&#xf…...

箱形理论在交易策略中的实战应用与优化

箱形理论&#xff0c;简单来说&#xff0c;就是将价格波动分成一段一段的方框&#xff0c;研究这些方框的高点和低点&#xff0c;来推测价格的趋势。 在上升行情中&#xff0c;价格每突破新高价后&#xff0c;由于群众惧高心理&#xff0c;可能会回跌一段&#xff0c;然后再上升…...

MinIO 和 Apache Tika:文本提取模式

Tl;dr: 在这篇文章中&#xff0c;我们将使用 MinIO Bucket Notifications 和 Apache Tika 进行文档文本提取&#xff0c;这是大型语言模型训练和检索增强生成 LLM和RAG 等关键下游任务的核心。 前提 假设我想构建一个文本数据集&#xff0c;然后我可以用它来微调 LLM.为了做…...

c编译器学习05:与chibicc类似的minilisp编译器(待续)

minilisp项目介绍 项目地址&#xff1a;https://github.com/rui314/minilisp 作者也是rui314&#xff0c;commits也是按照模块开发提交的。 minilisp只有一个代码文件&#xff1a;https://github.com/rui314/minilisp/blob/master/minilisp.c 加注释也只有996行。 代码结构&a…...

手撕qsort函数

前言 本篇主要讲解的是qsort函数细节以及运用实例。 紧跟我的脚步一起手撕qsort函数吧~ 欢迎关注​​个人主页&#xff1a;逸狼 更多优质内容&#xff1a; 拿捏c语言指针&#xff08;上&#xff09; 拿捏c语言指针&#xff08;中&#xff09; 拿捏c语言指针&#xff08;下&…...

项目在linux上的简单部署

本文章只介绍项目的简单部署&#xff0c;暂时没有Docker部署。 项目部署有两种方式&#xff0c;一种是直接命令部署&#xff0c;第二种是用脚本&#xff0c;脚本本身也是将命令进行封装来执行。 命令 项目通过maven打包&#xff0c;启动命令&#xff1a; # 启动命令 nohup …...

MySQL安装教程(详细版)

今天分享的是Win10系统下MySQL的安装教程&#xff0c;打开MySQL官网&#xff0c;按步骤走呀~ 宝们安装MySQL后&#xff0c;需要简单回顾一下关系型数据库的介绍与历史&#xff08;History of DataBase&#xff09; 和 常见关系型数据库产品介绍 呀&#xff0c;后面就会进入正式…...

Linux platform tree下的单总线驱动程序设计(DHT11)

目录 概述 1 认识DHT11 1.1 DHT11特性 1.2 DHT11数据格式 1.3 DHT11与MCU通信 1.4 DHT11信号解析 1.4.1 起始信号 1.4.2 解析信号0 1.4.3 解析信号1 2 驱动开发 2.1 硬件接口 2.2 更新设备树 2.2.1 添加驱动节点 2.2.2 编译.dts 2.2.3 更新板卡中的.dtb 2.3 驱…...

自研爬虫框架的经验总结(理论及方法)

背景&#xff1a; 由于业务需要&#xff0c;承接一部分的数据采集工作。目前市场内的一些通用框架不太适合。故而进行了自研。 对比自研和目前成熟的框架&#xff0c;自研更灵活适配&#xff0c;可以自己组装核心方法&#xff1b;后者对于新场景的适配需要对框架本身有较高的理…...

配置基于 AWS CRT 的 HTTP 客户端

基于 AWS CRT 的 HTTP 客户端包括同步 AwsCrtHttpClient 和异步 AwsCrtAsyncHttpClient。基于 AWS CRT 的 HTTP 客户端具有以下 HTTP 客户端优势&#xff1a; 更快的 SDK 启动时间 更小的内存占用空间 降低的延迟时间 连接运行状况管理 DNS 负载均衡 SDK 中基于 AWS CRT …...

挑战杯 基于LSTM的天气预测 - 时间序列预测

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 机器学习大数据分析项目 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng-senior/po…...

我为什么不喜欢关电脑?

程序员为什么不喜欢关电脑&#xff1f; 你是否注意到&#xff0c;程序员们似乎从不关电脑&#xff1f;别以为他们是电脑上瘾&#xff0c;实则是有他们自己的原因&#xff01;让我们一起揭秘背后的原因&#xff0c;看看程序员们真正的“英雄”本色&#xff01; 一、上大学时。 …...

Unity【角色/摄像机移动控制】【1.角色移动】

本文主要总结实现角色移动的解决方案。 1. 创建脚本&#xff1a;PlayerController 2. 创建游戏角色Player&#xff0c;在Player下挂载PlayerController脚本 3. 把Camera挂载到Player的子物体中&#xff0c;调整视角&#xff0c;以实现相机跟随效果 3. PlayerController脚本代码…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...