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

【保姆级图解】插入排序算法详解：直接插入排序、希尔排序

news 来源：原创 2025/9/16 11:26:29

总体引入

在计算机科学的算法领域中，排序是一项基础且重要的操作。它旨在将一组无序的数据元素重新排列为有序序列，以满足特定的顺序要求，如升序或降序。常见的排序算法可分为不同类别，像插入排序，包含直接插入排序和希尔排序；选择排序，有直接选择排序和堆排序；交换排序，涵盖冒泡排序和快速排序；还有归并排序。这些算法各有特点，适用于不同的应用场景，接下来让我们深入了解它们。

插入排序引入

想象你整理扑克牌时，会从一堆牌里一张一张拿出来，按顺序插到已经整理好的牌堆合适位置。编程里的插入排序差不多也是这个道理。它把数据分成已排序和未排序两部分，从未排序部分取元素，在已排序部分找到合适位置插入，不断重复，直到所有元素都排好序，就像把乱序的扑克牌整理成有序的一样。

一、直接插入排序（Insertion Sort）

算法思想：
将数组分为“已排序”和“未排序”两部分，逐个将未排序部分的元素插入到已排序部分的正确位置。

代码解析：

void InsertSort(int* arr, int n) {for (int i = 0; i < n - 1; i++) {  // 从第一个元素开始遍历到倒数第二个元素int end = i;                   // 已排序部分的末尾索引int tmp = arr[end + 1];        // 待插入元素（未排序部分的第一个元素）while (end >= 0) {             // 向前寻找插入位置if (arr[end] > tmp) {      // 若当前元素大于待插入元素，则后移arr[end + 1] = arr[end];end--;} else {                   // 找到合适位置，退出循环break;}}arr[end + 1] = tmp;            // 插入元素到正确位置}
}

步骤说明：

外层循环：遍历每个待插入元素（从第二个元素开始）。
内层循环：从后向前比较，若当前元素比待插入元素大，则将其后移。
插入操作：找到第一个比待插入元素小的位置，将元素插入其后。

复杂度分析：

时间复杂度：
- 最好情况（已有序）：O(n)，只需比较无需移动。
- 最坏情况（逆序）：O(n²)，每次插入需移动全部已排序元素。
空间复杂度：O(1)，原地排序。

适用场景：
数据量小或基本有序时效率高，稳定且简单。

二、希尔排序（Shell Sort）

算法思想：
希尔排序是对直接插入排序的一种改进算法，它通过将待排序的数组按照一定的间隔（称为增量）进行分组，对每组分别进行直接插入排序，逐步缩小增量，当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。

代码解析：

void ShellSort(int* arr, int n) {int gap = n;                       // 初始间隔设为数组长度while (gap > 1) {                  // 循环直到间隔为1（最后一次完整插入排序）gap = gap / 3 + 1;            // 动态调整间隔（常见增量方式）for (int i = 0; i < n - gap; i++) {  // 对所有间隔分组进行插入排序int end = i;               // 当前组的已排序末尾int tmp = arr[end + gap]; // 待插入元素while (end >= 0) {        // 组内插入排序if (arr[end] > tmp) {  arr[end + gap] = arr[end];end -= gap;        // 跨间隔移动} else {break;}}arr[end + gap] = tmp;      // 插入元素}}
}

步骤说明：

动态调整间隔：初始间隔较大，逐步缩小(gap = gap/3 + 1)或者(gap = gap/2)。
分组插入排序：对每个间隔形成的子序列进行插入排序。
最终排序：当间隔为1时，退化为标准插入排序，此时数组已基本有序。

复杂度分析：

时间复杂度：约 O(n^1.3)，依赖增量序列的选择。
空间复杂度：O(1)，原地排序。

适用场景：
中等规模数据，对稳定性无要求，优于直接插入排序。

测试案例

void test01() {int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};int size = sizeof(arr) / sizeof(arr[0]);// InsertSort(arr, size);ShellSort(arr, size);for (int i = 0; i < size; i++) {printf("%d ", arr[i]);  // 输出：0 1 2 3 4 5 6 7 8 9}
}

运行结果：
无论调用哪个排序函数，最终输出均为有序数组 0 1 2 3 4 5 6 7 8 9。

总结

直接插入排序：简单稳定，适合小数据或部分有序场景。
希尔排序：插入排序的高效改进，适合中等规模数据。

理解基础排序算法的实现有助于掌握更复杂的排序技术，实际应用中可根据数据特征选择合适的算法。

【保姆级图解】插入排序算法详解：直接插入排序、希尔排序

总体引入在计算机科学的算法领域中，排序是一项基础且重要的操作。它旨在将一组无序的数据元素重新排列为有序序列，以满足特定的顺序要求，如升序或降序。常见的排序算法可分为不同类别，像插入排序，包含直接插入排序和…...

编程日记 2025/9/16 11:26:29

Python爬虫第10节-lxml解析库用 XPath 解析网页

目录引言一、XPath简介二、XPath常用规则三、实例讲解四、节点的选取 4.1 所有节点的选取 4.2 子节点的选取 4.3 父节点选取五、属性匹配获取及文本获取 5.1 属性匹配 5.2 文本获取 5.3 属性获取 5.4 属性多值匹配 5.5 多属性匹配六、按序选择七、节点…...

编程日记 2025/9/15 17:36:31

Prometheus有哪几种服务发现？

Prometheus 支持多种服务发现 (Service Discovery) 机制，用于自动发现需要监控的目标。这些服务发现机制主要分为以下几类： 1. 静态配置 (Static Configuration) Static Configuration: 手动定义静态目标列表。适用于小规模的、固定的目标环境&#xf…...

编程日记 2025/9/16 11:15:03

突破焊丝虚影干扰，端子焊点缺陷检测如何实现自动化？

端子焊点作为 3C 产品中连接电路的关键环节，其质量优劣对产品性能有着决定性影响。然而，传统人工检测端子焊点不仅效率低下，难以满足大规模生产需求，而且误判率高，无法精准把控产品质量，成为企业提质增效智…...

编程日记 2025/9/16 11:15:02

2025.04.10-拼多多春招笔试第二题

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 02. 糖果店的优惠兑换计划问题描述 K小姐开了一家糖果店，推出了一种特殊的兑换活动。商店有 n n n<...

编程日记 2025/9/16 11:23:39

linux系统下如何提交git和调试

我们默认的ubuntu20.04镜像是没有Git提交的工具，我们需要配置安装包。安装和更新git的命令 sudo apt update //用于更新软件包索引sudo apt install git //用于安装git版本控制工具 git --version //检查git版本,确认是否安装成功随便进入linux系统下的一…...

编程日记 2025/9/16 11:23:38

40页的IPD流程指标字典【全文精读】

该文档聚焦 IPD 流程指标，为企业在产品研发管理领域提供全面量化评估标准，主要适用于企业中与产品研发、管理、财务及市场相关的各类人员。财务类指标：涵盖市场份额、新产品销售比重等，用于评估产品市场竞争力、投资效率…...

编程日记 2025/9/16 11:25:18

如何在Cherry Studio中配置MCP工具服务？国内MCP服务有哪些？

在当今数字化时代，AI助手已成为提升工作效率和创造力的重要工具。Cherry Studio作为一个全能的AI客户端，支持多平台（包括Windows、macOS和Linux），并提供了丰富的功能，如大模型对话、AI绘图和AI翻译等。为了…...

编程日记 2025/9/16 11:17:32

动态词槽管理系统深度设计

动态词槽管理系统深度设计基于Dual-Encoder的实时增量式语义槽管理方案一、Dual-Encoder架构优化 1.1 架构创新设计增强型双塔模型结构： #mermaid-svg-DRhtmuANYnJBJzpu {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill…...

编程日记 2025/9/12 16:20:00

网络安全中信息收集需要收集哪些信息了？汇总

目录 1. 域名信息 2. IP地址与网络信息 3. 备案与注册信息 4. Web应用与中间件信息 5. 操作系统与服务器信息 6. 敏感文件与配置文件 7. 社交工程信息 8. 证书与加密信息 9. API与接口信息 10. 外部威胁情报 11. 历史数据与缓存常用工具与技术： 在网络…...

编程日记 2025/9/9 16:10:08

代码模板-线段树（区间修改，区间查询和和最值）

题目链接：1270. 数列区间最大值 - AcWing题库代码： // #pragma GCC optimize(1) // #pragma GCC optimize(2) // #pragma GCC optimize(3,"Ofast","inline")#include<bits/stdc.h> using namespace std; typedef long long…...

编程日记 2025/9/15 6:26:15

LLM介绍

一、核心概念与能力边界 LLM（Large Language Model：大语言模型）是基于海量文本训练的深度学习模型，其核心能力源于Transformer架构与自监督学习机制。关键特征包括： 参数规模：千亿级参数（如GP…...

编程日记 2025/9/11 10:35:43

[数据结构]排序

目录 1、排序的概念 2、常见排序算法 3、直接插入排序 4、希尔排序 5、直接选择排序 6、堆排序 7、冒泡排序 1、排序的概念排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作 …...

编程日记 2025/9/7 10:00:20

Next.js + Droplet：高并发视频内容平台部署与优化扩展实战

在构建在线服务时，无论你是开发者还是企业技术负责人，扩展性和稳定性始终是绕不开的核心挑战。尤其在涉及高并发访问、大量数据传输和持续内容分发的场景中，系统架构的设计直接决定了用户体验与业务成效。本文将以视频点播（Video…...

编程日记 2025/9/10 9:55:47

django寻味美食分享与交流网站-计算机毕业设计源码74984

摘要美食分享与交流网站是当前社交网络领域的一个热门话题。本研究旨在探讨用户在美食分享网站上的行为和互动模式，以及他们分享和获取美食信息的动机和方式。通过对美食分享网站上用户发文内容和互动数据的分析，揭示了用户在美食分享中的需求和行为规…...

编程日记 2025/9/16 0:52:11

把读写函数里的printf 打印到文件里

使用 fprintf 函数将输出目标从标准输出（stdout）更改为一个文件指针 1、首先，在头文件或全局变量中定义一个 FILE 类型的指针，用于指向输出文件。 2、在程序启动时，打开文件并将文件指针赋值给上面定义的全局指针。…...

编程日记 2025/9/3 17:48:20

在idea中看spring源码

一、搭建环境 1.1 下载源码到本地在github中找到spring-framework项目，或者这个地址（https://github.com/spring-projects/spring-framework） 然后把项目下载到本地目录，如图 1.2 然后用idea打开这个项目 1.3 然后等构建&…...

编程日记 2025/9/9 20:28:55

用最简单的方式讲述离散傅里叶级数（DFS）以及离散傅立叶变换（DFT）

文章目录前言一、傅里叶变换的多种形式二、浅谈离散傅里叶级数（DFS） 三、浅谈离散傅里叶变换（DFT） 总结前言本文对四种不同的傅里叶变换做了总结与梳理，并针对其中存在联系的形式做了推导。接着又讲述了离散傅里叶…...

编程日记 2025/9/11 19:01:47

python基础语法14-多线程与多进程

Python 多线程与多进程详解在 Python 中，多线程和多进程是常用的并发编程技术，它们可以帮助程序在处理大量任务时提高效率。Python 提供了多个模块来支持多线程和多进程的开发，包括 threading、multiprocessing 和 asyncio。本文将详细介绍…...

编程日记 2025/9/11 10:18:39

深入解析策略模式在C#中的应用与实现

策略模式（Strategy Pattern）是一种行为型设计模式，它通过将一系列算法封装成不同的策略类，使得算法的选择和使用可以在运行时动态改变，且算法的变化对使用者透明。这种模式可以显著减少程序中的条件判断（如…...

编程日记 2025/9/10 15:12:19

ios按键精灵脚本开发游戏辅助工具的代码逻辑

iOS 按键精灵使用 MQ 语言开发游戏脚本，其代码逻辑围绕游戏内的各种操作展开。我将从常见的游戏操作，如点击、移动等方面， 点击操作逻辑在游戏中，点击操作是最基础的交互方式之一。比如要实现点击游戏界面上某个固定位置的 “…...

编程日记 2025/9/8 18:19:18

Pycharm（十三）容器类型的公共运算符和公共方法

一、容器类型的公共运算符这些运算符是可以作用到容器类型中的。常见的如下： ：拼接，适用于字符串、列表、元组； *：复制，适用于字符串、列表、元组； in:是否包含,适用于字符串、列表、元…...

编程日记 2025/9/9 1:32:00

Backtrader从0到1——第一个回测策略

Backtrader从0到1——第一个回测策略 0. 前言1. lines && index2. 生成大脑3. 设置起始资金和佣金4. 添加数据（重点）5. 第一个策略——双均线5.1 策略类5.2 策略参数5.3 添加指标5.4 买卖与订单order5.5 完整策略代码 0. 前言本人翻阅了大量资料…...

编程日记 2025/9/15 14:53:07

GPT - 因果掩码（Causal Mask）

本节代码定义了一个函数 causal_mask，用于生成因果掩码（Causal Mask）。因果掩码通常用于自注意力机制中，以确保模型在解码时只能看到当前及之前的位置，而不能看到未来的信息。这种掩码在自然语言处理任务（如…...

编程日记 2025/9/9 11:22:47

我使用lombok的Data注解带来的坑。代码如下： 公共类： package com.tyler.oshi.common;import lombok.Data; import lombok.NoArgsConstructor;/*** author: TylerZhong* description:*/Data NoArgsConstructor public class R {private int code;priv…...

编程日记 2025/9/16 4:57:13

基于Python的网络爬虫技术研究

基于Python的网络爬虫技术研究以下从多个方面为你介绍基于 Python 的网络爬虫技术： 概述网络爬虫是一种自动获取网页内容的程序，在 Python 中可以借助诸多强大的库和工具实现。网络爬虫能应用于数据采集、搜索引擎、舆情监测等众多领域。核心库 …...

编程日记 2025/9/13 11:26:57

微信小程序跳6

//金额格式化 rmoney: function(money) { return parseFloat(money).toFixed(2).toString().split().reverse().join().replace(/(\d{3})/g, $1,) .replace( /\,$/, ).split().reverse().join(); }, daysUntil: function(milliseconds) { const endDate new Date(milliseconds…...

编程日记 2025/8/26 22:14:03

总体引入

插入排序引入

一、直接插入排序（Insertion Sort）

二、希尔排序（Shell Sort）

测试案例

总结

相关文章：