常用排序算法之插入排序
目录
前言
一、基本原理
1.算法步骤
2.动画演示
3.插入排序的实现代码
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
2.最差时间复杂度
3.平均时间复杂度
2. 空间复杂度
三、插入排序的优缺点
1.优点
2.缺点
四、插入排序的改进与变种
五、插入排序的应用场景
六、总结
前言
插入排序(Insertion Sort)是一种简单且直观的排序算法,常用于小规模数据的排序或作为其他复杂排序算法的一部分(如快速排序的小数组优化)。
本文将详细介绍插入排序的基本原理、实现代码、时间复杂度及其适用场景,帮助你轻松掌握这一算法。
一、基本原理
插入排序的核心思想是将数组分为已排序部分和未排序部分。通过逐一从未排序部分取出元素,将其插入到已排序部分的合适位置,最终完成排序。
1.算法步骤
1. 从数组的第二个元素开始,视为当前需要插入的元素。
2. 从已排序部分的最后一个元素开始比较,如果当前元素较小,则将已排序部分元素向右移动。
3. 重复上述步骤,直到找到插入位置,将当前元素插入。
4. 对剩余的未排序部分重复以上步骤,直至整个数组有序。
2.动画演示
这里我写了一个程序用来演示直接插入算法的过程。
假如我要进行排序的数据元素分别为5,3,, 8,6,2,7,4,1。
初始的时候,我们已排序中的部分中的数据元素使用绿色表示,未排序的使用蓝色表示。

图1.初始状态
初始状态下,我们把第一个数据元素看做一个已经排列好的部分。
同时把第二个数据元素作为下次要插入的数据元素。

图2.插入排序的动画演示
我们以上面的数组为例看一下具体的过程:
5,3, 8,6,2,7,4,1
1.第一轮
首先确定5是已经排列好的,我们将3进行插入操作。将3插入到仅有一个数据元素为5的数组中,显然5比3大,我们将3插入到5的前面。至此第一轮插入结束。此时的数组为{3,5,8,6,2,7,4,1}。
2.第二轮
在上一轮中,已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为5<8,依次已排序区间应该为{3,5,8}。第二轮结束,此时排序依然是{3,5,8,6,2,7,4,1}。
2.第二轮
在上一轮中,已排序的区间为{3,5},现在我们将8拿出来和前面排列好的部分进行比较。因为5<8,依次已排序区间应该为{3,5,8}。第二轮结束,此时排序依然是{3,5,8,6,2,7,4,1}。
3.第三轮
在上一轮中,已排序的区间为{3,5,8},现在我们将6拿出来和前面排列好的部分进行比较。因为8>6,我们在把6和前面的一个数据元素5比较,5<6,把6查到5后面,依次已排序区间应该为{3,5,6,8}。第二轮结束,此时排序依是{3,5,6,8,2,7,4,1}。
4.第四轮
在上一轮中,已排序的区间为{3,5,6,8},现在我们将2拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同,这里不重复了,此时排序是{2,3,5,6,8,7,4,1}。
5.第五轮
在上一轮中,已排序的区间为{2,3,5,6,8},现在我们将7拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同,这里不重复了,此时排序是{2,3,5,6,7,8,4,1}。
3.第六轮
在上一轮中,已排序的区间为{2,3,5,6,7,8},现在我们将4拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同,这里不重复了,此时排序是{2,3,4,5,6,7,8,1}。
3.第三轮
在上一轮中,已排序的区间为{2,3,4,5,6,7,8},现在我们将1拿出来和前面排列好的部分进行比较。具体的比较过程和上一轮相同,这里不重复了,此时排序是{1,2,3,4,5,6,7,8}
3.插入排序的实现代码
以下是插入排序的 C语言实现:
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i]; // 当前要插入的元素int j = i - 1;// 将比 key 大的元素向右移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}// 插入 key 到正确的位置arr[j + 1] = key;// 打印当前排序步骤printf("第 %d 步: ", i);for (int k = 0; k < n; k++) {printf("%d ", arr[k]);}printf("\n");}
}
int main(int argc, const char * argv[]) {int arr[] = {5, 3, 8, 6, 2, 7, 4, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 执行插入排序insertionSort(arr, n);// 打印排序后的数组printf("排序后数组: ");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}
二、插入排序的时间复杂度
1. 时间复杂度
1.最优时间复杂度
当数组已经有序时,每次插入只需比较一次,无需移动元素。
2.最差时间复杂度
当数组为逆序时,每次插入都需要将所有已排序部分元素向右移动。
3.平均时间复杂度
一般情况下,插入排序的性能表现介于最佳和最差之间。
2. 空间复杂度
插入排序是原地排序算法,只需常数级别的额外空间,空间复杂度为O(1) 。
三、插入排序的优缺点
1.优点
1. 简单直观:算法易于理解和实现。
2. 适合小数据集:对于小规模数据排序性能较好。
3. 稳定性:插入排序是稳定排序算法,不会改变相同元素的相对位置。
4. 局部有序优化:当数据部分有序时,插入排序的性能非常接近线性时间。
2.缺点
1. 效率低下:对于大规模数据,插入排序的性能较差,时间复杂度较高。
2. 多次元素移动:在数组为逆序的情况下,插入排序需要频繁移动元素,效率较低。
四、插入排序的改进与变种
1. 二分插入排序
• 改进点:在插入时,通过二分查找定位插入位置,从而减少比较次数。
• 时间复杂度:虽然查找位置优化为 ,但元素移动次数仍为 。
2. 希尔排序(Shell Sort)
• 基于插入排序的改进版,通过引入增量分组的思想,对远距离元素进行预排序,逐步缩小分组间隔,最终变为插入排序。
• 时间复杂度:最优可达 。
五、插入排序的应用场景
1. 小规模数据排序:在数据量较小时,插入排序简单易用,且性能尚可。
2. 近乎有序数据:插入排序在处理已部分有序的数据时表现优异。
3. 作为复杂排序的辅助算法:如快速排序或希尔排序中,用插入排序优化小数组的排序效率。
六、总结
插入排序是一种经典的排序算法,以其简单性和直观性被广泛应用于教学和小规模排序场景中。虽然它在大数据排序上的性能较差,但通过改进(如二分插入排序)或结合其他算法(如希尔排序),可以显著提升效率。
相关文章:
常用排序算法之插入排序
目录 前言 一、基本原理 1.算法步骤 2.动画演示 3.插入排序的实现代码 二、插入排序的时间复杂度 1. 时间复杂度 1.最优时间复杂度 2.最差时间复杂度 3.平均时间复杂度 2. 空间复杂度 三、插入排序的优缺点 1.优点 2.缺点 四、插入排序的改进与变种 五、插入排…...
Elasticsearch(ES)基础查询语法的使用
1. Match Query (全文检索查询) 用于执行全文检索,适合搜索文本字段。 { “query”: { “match”: { “field”: “value” } } } match_phrase:精确匹配短语,适合用于短语搜索。 { “query”: { “match_phrase”: { “field”: “text” }…...
一篇文章学会Milvus【Docker 中运行 Milvus(Windows),Python实现对Milvus的操作,源代码案例,已经解决巨坑】【程序员猫爪】
一篇文章学会Milvus【Docker 中运行 Milvus(Windows),Python实现对Milvus的操作,源代码案例,已经解决巨坑】【程序员猫爪】 一、Milvus 是什么?【程序员猫爪】1、Milvus 是一种高性能、高扩展性的向量数据库…...
前端之移动端
视口 布局视口 layout viewport 视口(viewport)就是浏览器显示页面内容的屏幕区域。 视口可以分为布局视口、视觉视口和理想视口 一般移动设备的浏览器都默认设置了一个布局视口,用于解决早期的PC端页面在手机上显示的问题。 iOS, Androi…...
记一次 SpringBoot 启动慢的问题
记一次 SpringBoot 启动慢的问题 背景问题描述分析处理Flame Graph 火焰图Call Tree 调用树关键词检索尝试解决 为什么这样反向检索问题梳理 复盘处理流程为什么 Reference 背景 最近临时接了一个任务,就从一个旧 springboot 项目 copy 出来,临时写个服…...
高效安全文件传输新选择!群晖NAS如何实现无公网IP下的SFTP远程连接
文章目录 前言1. 开启群晖SFTP连接2. 群晖安装Cpolar工具3. 创建SFTP公网地址4. 群晖SFTP远程连接5. 固定SFTP公网地址6. SFTP固定地址连接 前言 随着远程办公和数据共享成为新常态,如何高效且安全地管理和传输文件成为了许多人的痛点。如果你正在寻找一个解决方案…...
如何在Python中进行JSON数据的序列化和反序列化?
在Python中,JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。Python内置的json模块提供了简单易用的方法来实现数据的序列化和反序列化。下面将详细介绍如何…...
学习记录-统计记录场景下的Redis写请求合并优化实践
学习记录-使用Redis合并写请求来优化性能 1.业务背景 学习进度的统计功能:为了更精确的记录用户上一次播放的进度,采用的方案是:前端每隔15秒就发起一次请求,将播放记录写入数据库。但问题是,提交播放记录的业务太复杂了&#x…...
网站HTTP改成HTTPS
您不仅需要知道如何将HTTP转换为HTTPS,还必须在不妨碍您的网站自成立以来建立的任何搜索排名权限的情况下进行切换。 为什么应该从HTTP转换为HTTPS? 与非安全HTTP于不同,安全域使用SSL(安全套接字层)服务器上的加密代…...
如何在龙蜥 OS(AliOS)上安装极狐GitLab?
本文分享如何在龙蜥操作系统(AliOS)(包括 RHCK 和 ANCK 两种,两种方式的安装流程一样)上安装极狐GitLab? 前提条件 一个安装了龙蜥操作系统的云服务器 可以查看 /etc/os-release中的信息,确认…...
unity插件Excel转换Proto插件-ExcelToProtobufferTool
unity插件Excel转换Proto插件-ExcelToProtobufferTool **ExcelToProtobufTool 插件文档****1. 插件概述****2. 默认配置类:DefaultIProtoPathConfig****属性说明** **3. 自定义配置类****定义规则****示例代码** **4. 使用方式****4.1 默认路径****4.2 自定义路径**…...
C#中的语句
C#提供了各式各样的语句,大多数是由C和C发展而来,当然,在C#中做了相应修改。语句和表达式一样,都是C#程序的基本组成部分,在本文我们来一起学习C#语句。 1.语句 语句是构造所有C#程序的过程构造块。在语句中可以声明…...
《罗宾逊-旅途VR》Build2108907官方学习版
《罗宾逊-旅途VR》官方版 https://pan.xunlei.com/s/VODiY5gn_fNxKREdVRdwVboCA1?pwdsh3f# 从第一人称的角度进行探索,玩家将遇到一系列恐龙和生物,这些恐龙和生物会对它们在泰森三世生态系统中的存在做出反应。强调与周围环境的互动,鼓励玩…...
常用的跨域方案有哪些?
在前端开发中,跨域(Cross-Origin)是一个常见问题,通常是由于浏览器的同源策略(Same-Origin Policy)限制导致的。为了解决跨域问题,前端开发者可以采用多种方案。 1. CORS(跨域资源共…...
JDBC实验测试
一、语言和环境 实现语言:Java。 环境要求:IDEA2023.3、JDK 17 、MySQL8.0、Navicat 16 for MySQL。 二、技术要求 该系统采用 SWING 技术配合 JDBC 使用 JAVA 编程语言完成桌面应用开发。 三、功能要求 某电商公司为了方便客服查看用户的订单信…...
ChatGPT 摘要,以 ESS 作为你的私有数据存储
作者:来自 Elastic Ryan_Earle 本教程介绍如何设置 Elasticsearch 网络爬虫,将网站索引到 Elasticsearch 中,然后利用 ChatGPT 使用我们的私人数据来总结对其提出的问题。 Python 脚本的 Github Repo:https://github.com/Gunner…...
每日一题洛谷P2669 [NOIP2015 普及组] 金币c++
#include<iostream> using namespace std; int main() {int k;cin >> k;int sum 0;int n 1;while (k > 0) {sum n * n;k - n;n;}sum k * (n - 1);cout << sum << endl;return 0; }...
【C语言系列】深入理解指针(2)
一、数组名的理解 上一篇文章中我们写过一个这样的代码: int arr[10] {1,2,3,4,5,6,7,8,9,10}; int *p &arr[0];这里使用&arr[0] 的方式拿到了数组第⼀个元素的地址,但是其实数组名本来就是地址,而且是数组首元素的地址ÿ…...
与 Spring Boot 的无缝集成:ShardingSphere 快速集成实践
ShardingSphere 是一个轻量级的开源分布式数据库中间件,它支持分库分表、分布式事务、读写分离等功能。它能够与各种应用框架进行集成,其中与 Spring Boot 的集成非常流行,因为它能够帮助开发者在 Spring Boot 项目中快速实现高性能的分布式数…...
【QT】窗口/界面置于最前端显示,且激活该窗口
目录 0.环境 1.问题描述 2.具体实现 0.环境 windows11 qt 1.问题描述 我有一个窗口QMainWindow(也适用于QWidget或QDialog),想让其在显示的时候置于最前面,且激活成为当前活动窗口 2.具体实现 mainWindow->show();mainWind…...
新手程序员必看:7类常见错误与高效解决方案
1. 新手程序员常犯的7类错误及解决方案作为一名带过5届应届生的技术导师,我发现每一批新人都会重复踩同样的坑。最近带的这位应届生让我想起了自己刚入行时的样子——充满热情但缺乏方法。下面这些经验教训,都是我亲自踩过坑后总结出来的实战心得。提示&…...
忍者像素绘卷:天界画坊卷积神经网络原理与应用:解析像素风格生成内核
忍者像素绘卷:天界画坊卷积神经网络原理与应用 1. 卷积神经网络基础入门 在开始探索忍者像素绘卷的神奇世界之前,我们需要先了解支撑它的核心技术——卷积神经网络(CNN)。CNN就像一位精通像素艺术的数字画家,能够从原始图像中提取特征&…...
Phi-4-mini-reasoning模型微调入门:使用自有数据提升领域推理能力
Phi-4-mini-reasoning模型微调入门:使用自有数据提升领域推理能力 1. 为什么需要微调推理模型 在实际业务场景中,通用大模型虽然具备强大的推理能力,但在特定领域的表现往往不尽如人意。比如在法律条文解读或医疗诊断建议这类专业领域&…...
OpenClaw+千问3.5-9B低成本方案:自建模型替代OpenAI API
OpenClaw千问3.5-9B低成本方案:自建模型替代OpenAI API 1. 为什么选择自建模型替代OpenAI API 去年冬天的一个深夜,我正在调试一个基于OpenClaw的自动化工作流。当看到账单上OpenAI API调用费用突破四位数时,我意识到必须寻找替代方案。这就…...
Python爬虫实战:用Qwen2.5-VL智能解析网页图片内容
Python爬虫实战:用Qwen2.5-VL智能解析网页图片内容 1. 引言 你有没有遇到过这样的情况:爬取了大量网页图片,却要人工一张张查看内容?或者需要从海量图片中筛选出特定类型的商品、识别图中的文字信息?传统爬虫只能获取…...
FPGA直方图均衡化/直方图拉伸/FPGA图像处理 工程和算法包含以下内容: 1,MATLAB...
FPGA直方图均衡化/直方图拉伸/FPGA图像处理 工程和算法包含以下内容: 1,MATLAB中实现图像处理。 2,verilog代码利用MATLAB联合modelsim仿真实现的图像处理。 3,小梅哥AC620和正点原子新起点/开拓者的FPGA板卡上实现的图像处理。 4…...
像素幻梦惊艳案例:FLUX.1-dev生成符合PICO-8硬件限制的像素程序截图
像素幻梦惊艳案例:FLUX.1-dev生成符合PICO-8硬件限制的像素程序截图 1. 像素艺术的新纪元 在复古游戏复兴的浪潮中,像素艺术正迎来它的第二次黄金时代。而FLUX.1-dev模型的出现,为这种经典艺术形式注入了全新的活力。今天我们要展示的&…...
协程设计原理与汇编实现:从原语到网络IO Hook
一、为什么需要协程?在高并发网络编程中,我们面临一个经典矛盾:同步编程简单但性能差,异步编程性能高但代码复杂。协程的出现,正是为了用同步的写法获得异步的性能。1.1 同步与异步的本质同步:串行执行&…...
BAAI/bge-m3新手指南:无需代码基础,也能玩转高级语义分析模型
BAAI/bge-m3新手指南:无需代码基础,也能玩转高级语义分析模型 1. 什么是BAAI/bge-m3语义分析引擎 1.1 模型的基本功能 BAAI/bge-m3是一个强大的语义分析工具,它能理解文本背后的含义而不仅仅是表面的词语。想象一下,当你说&quo…...
从命令到思想:Shell脚本编程的“一课一得”
引言在Linux系统学习的旅程中,Shell脚本编程是一个绕不开的重要关卡。在此之前,我们只是在命令行中逐条输入指令,像一个机械的执行者;在此之后,我们开始将自己的思路封装成可复用的逻辑,成为一个真正的设计…...
