七大排序之直接插入排序

简介: 七大排序之直接插入排序

时间复杂度:  ~

空间复杂度:

稳定性:  稳定      

1、基本思想

直接插入排序是一种简单的插入排序法,其思想就是把待排序的数按照其大小逐个插入到一个已将排好的有序序列中,直到所有的记录插入完为止。

实际中,我们在玩扑克牌时,就与运用了插入排序的思想。

2、代码讲解和实现

       当插入第i(i>=1)个元素时,前面的array[0]、array[1].....array[i-1] 已经排好序。

第一步:定义一个 j 变量并赋值为i-1,同时定义一个 val 变量存储一下 array[i]的值。


第二步:让array[j] 与 val 进行比较


       如果 array[j] 大于 val , 就把array[j]向前挪一步,也就是 array[j+1] = array[j]。


       如果 array[j] 小于等于 val,就把 val 放到 array[j+1]中。

j 必须 大于等于0 ,要不然会越界。

  public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int j = i-1;
            int val = array[i];
            for(; j >= 0 ; j--){
                if(array[j] > val){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1]= val;
        }

3、特性总结

3.1 时间复杂度:

当数据有序时,直接插入排序耗时最少,为

数据有序时,外循环每遍历一个元素,都比前 i-1个元素都大,内循环相当于没有执行。总的时间就是遍历数组的时间。

当数据逆序时,耗时最多,为

数据逆序,每次插入第 i 个元素,内循环都要遍历 i-1 次。当 n 数排序完,也就是遍历了 次

3.2 空间复杂度:

      因为直接插入排序是内部排序,所以空间复杂度为

3.3 适合场景:

       当数据基本上是有序的时候,使用直接插入排序

相关文章
|
1月前
|
存储 弹性计算 固态存储
阿里云服务器价格:轻量38元1年、ECS云服务器99元和199元配置指南
2026年阿里云服务器最新报价:轻量应用服务器低至38元/年(2核2G、200M峰值带宽、不限流量);ECS经济型e实例99元/年起,企业级c9i/g9i/r9i等规格丰富,支持包年包月、按量付费等多种计费模式。
252 0
|
1月前
|
人工智能 IDE API
阿里云 Qoder CN 智能编码平台实战教程:本地 IDE 插件配置、终端 CLI 操作、云端 Agent 部署与开放 API 接入全流程
AI编程已经从简单的代码片段生成,进化到智能体自主完成工程任务的新阶段。Qoder CN不是简单的代码补全插件,而是一套完整面向软件研发的AI智能体平台,覆盖IDE桌面、终端CLI、云端托管、数字员工多条产品线,深度对接百炼平台订阅体系,依托强大的工程上下文感知、Quest自主任务模式、MCP扩展能力,把自然语言需求转化为可运行的工程代码。对于个人开发者,它降低编码负担,专注业务逻辑设计;对于中小型团队,不需要复杂二次开发,就可以引入AI研发能力,缩短项目交付周期;对于大型企业,企业级版本提供权限管控、审计、私有知识库,在合规前提下放大AI带来的研发收益。随着智能体技术持续迭代,编程智能体会深
444 0
|
2月前
|
缓存 监控 小程序
小程序发版总翻车?灰度发布、实时监控与快速回滚的落地设计
小程序发版最怕三件事:全量发布直接崩、出问题回滚慢、用户手机里一直是旧版本。本文给一套发版流程设计:体验版到提审到灰度再到全量的关卡划分、灰度比例与自动放量、监控卡点与快速回滚、版本号与缓存更新策略,附发版检查清单与配置表。适用于小程序/轻应用产品的版本发布管理。
|
4月前
|
存储 API 数据库
RAG检索增强怎么搭建:从原理到落地的完整路径
RAG(检索增强生成)通过“先检索、再生成”机制,将外部知识库与大模型结合,解决幻觉、数据过时及私有数据不可用问题。涵盖文档解析、文本分块、向量化存储、检索生成四大环节,强调分块策略、检索质量与提示词约束的协同优化。(239字)
|
5月前
|
数据安全/隐私保护
一文说清while循环、do-while循环、for循环
一文说清while循环、do-while循环、for循环
|
5月前
|
SQL 存储 关系型数据库
MySQL迁移国产数据库实战:从双写到灰度切换,业务零中断的完整方案
MySQL迁移常被低估难度——以为“都是开源数据库应该差不多”,实际却面临数据类型差异、事务隔离机制不同、存储引擎行为不一致等深层问题。本文从MySQL迁移的行业现状出发,梳理数据类型映射、语法差异、零停机迁移三大核心挑战,提供一套从兼容性评估到灰度切换的完整迁移路径,以及迁移工具选型和避坑要点。
|
人工智能 监控 JavaScript
MCP实战之Agent自主决策-让 AI玩转贪吃蛇
MCP服务器通过提供资源、工具、提示模板三大能力,推动AI实现多轮交互与实体操作。当前生态包含Manus、OpenManus等项目,阿里等企业积极合作,Cursor等工具已集成MCP市场。本文以贪吃蛇游戏为例,演示MCP Server实现流程:客户端连接服务端获取能力集,AI调用工具(如start_game、get_state)控制游戏,通过多轮交互实现动态操作,展示MCP在本地实践中的核心机制与挑战。
1267 39
MCP实战之Agent自主决策-让 AI玩转贪吃蛇
|
算法
海明码详解
本文详细介绍了海明码(Hamming Code)的概念、原理和应用,包括信息位与校验位的关系、校验位的计算方法、错误检测与纠正过程,并通过实例展示了如何使用海明码进行编码,突出了海明码在提高数据传输可靠性方面的重要性。
3005 0
海明码详解
|
调度 C++
PV操作知识点
PV操作知识点
1539 1