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

数据结构入门-14-排序

news 2026/3/27 10:39:31

在这里插入图片描述

一、选择排序

1.1 选择排序思想

先把最小的元素拿出来
剩下的，再把最小的拿出来
剩下的，再把最小的拿出来
在这里插入图片描述

但是这样 空间复杂度是O(n)
优化一下，希望原地排序

1.1.2 选择原地排序

在这里插入图片描述

索引i指向0的位置
索引j指向i+1的元素
j 后面的元素遍历，找到最小的标记为minindex
交换minindex 和 i
在这里插入图片描述

时间复杂度O(n^2)
空间复杂度O(1)

1.2 选择排序复杂度

在这里插入图片描述
第一轮 n 次，第二轮 n-1 次
1 + 2 + 3 + … + (n-1) + n

二、插入排序

在这里插入图片描述

扑克牌的排序 就是 插入排序

2.1 插入排序思想

在这里插入图片描述

在这里插入图片描述

j 往前 插入
在这里插入图片描述

时间复杂度O(n^2)
空间复杂度O(1)

三、冒泡排序

基本思想：每次比较相邻的元素

3.1 冒泡基本思想

  1. 第一轮两两比较大小

在这里插入图片描述
如果 > ,就互换
在这里插入图片描述
一直到最后
在这里插入图片描述
第一轮之后，最大的元素一定在最后
所以在第二轮，最后一个元素就不用比较了

  1. 第二轮
    在这里插入图片描述
  2. 第三轮
    在这里插入图片描述
  3. 第n - 1轮
    在这里插入图片描述

3.2 冒泡过程理解

在这里插入图片描述

平均时间复杂度：O(n^2)
空间复杂度O(1)

一、归并排序MergeSort

更加复杂的递归算法

O(nlogn)的时间复杂度

1.1 归并思想

在这里插入图片描述
将一个数组一分为二 ，分别排序，得到两个排序后的子数组

在这里插入图片描述

对两个子数组排序的方法还是继续划分

MergeSort(arr, l, r)
对 arr数组的 l 到 r 区间进行排序

1.2 归并步骤

  1. 递归排序的算法：
MergeSort(arr, l, r)
  1. 找到切分的中点
int mid = (l + r) / 2
  1. 对arr[l , mid] 进行排序
MergeSort(arr, l, mid)
  1. 对arr[mid + 1, r] 进行排序
MergeSort(arr, mid+1, r)
  1. 将arr[l,mid] 和 arr[mid+1,r]进行合并
merge(arr, l, mid, r)
  1. 设置递归调用的终止条件
if(l >= r) return;

在这里插入图片描述

1.3 归并merge过程思想

在这里插入图片描述

  1. A[1] 和 B[1] 对比，谁更小，谁进入Result
    在这里插入图片描述
  2. 持续对比头上的点
    在这里插入图片描述

1.4 merge 过程详解

  1. 计算mid
    在这里插入图片描述

  2. 将数据复制一份，标记左右 i ， j = mid + 1
    在这里插入图片描述

  3. 使用i j 两个索引 对比，result 直接写入原区间
    在这里插入图片描述

  4. 终止条件：i >= mid , j > r
    在这里插入图片描述
    在这里插入图片描述
    归并排序过程无法原地完成

1.5 归并复杂度分析

空间复杂度：由于需要 copy 一份出来，所以是O(n)

时间复杂度：

在这里插入图片描述
MergeSort：每一层总和都会有 n
一共有 logn层

所以是O(n logn)

在这里插入图片描述

二、希尔排序

冒泡排序每次只能一位
希尔排序希望 很大的元素能够很快的移动到最后面

2.1 希尔排序思想

  1. 距离为4 （n/2）分组
    在这里插入图片描述

  2. 每一组内，元素进行插入排序
    在这里插入图片描述
    完成一轮组内的插入排序之后
    在这里插入图片描述

  3. 距离为2 （n/4）分组
    在这里插入图片描述

  4. 再次组内插入排序
    在这里插入图片描述

  5. 距离为（n/8）的排序
    由于只有8个，所以也就是array本身
    全体进行插入排序

在这里插入图片描述

2.2 为什么中间要用插入排序

希尔排序经过前面的分组内排序之后，
数组已经大体上都是有序的了
插入排序只需要找到前面一个不小于的即可
因此 最后 插入排序会省一些前面的比较步骤

在这里插入图片描述

2.3 希尔排序的复杂度

在这里插入图片描述
在这里插入图片描述

因此也称为 O(n^1.5)

相关文章：

数据结构入门-14-排序

一、选择排序 1.1 选择排序思想 先把最小的元素拿出来 剩下的，再把最小的拿出来 剩下的，再把最小的拿出来 但是这样 空间复杂度是O(n) 优化一下，希望原地排序 1.1.2 选择原地排序 索引i指向0的位置 索引j指向i1的元素 j 后面的元素遍历&…...

编程日记 2023/9/23 11:44:52

Gin学习记录4——Controller和中间件

一. Controller 用不同的Controller可以实现业务的分类，不同类型的请求可以共用同一套中间件 1.1 单文件Controller 几乎等同于函数封装，直接将ctrl的代码写入到一个文件里然后调用： package adminimport ("net/http""git…...

编程日记 2023/9/23 11:43:51

FL Studio21.2中文版数字音乐制作软件

现在的FL也可以像splice一样啦，需要什么样的声音只需在fl里搜索，就会自动展示给你! FL Studio 简称FL，全称：Fruity Loops Studio，国人习惯叫它"水果"。软件现有版本是 FL Studio 21，已全面升级支…...

编程日记 2023/9/23 11:41:49

ELK 企业级日志分析系统 ELFK

目录 一、概述 二、组件介绍 2.1、ElasticSearch 2.2、Kiabana 2.3、Logstash 2.4、可以添加的其它组件：Filebeat 2.5、缓存/消息队列（redis、kafka、RabbitMQ等） 2.6、Fluentd 三、ELK工作原理 四、实例演示 1.ELK之 部署"E&q…...

编程日记 2023/9/23 11:40:48

IDEA中创建Java Web项目方法1

以下过程使用IntelliJ IDEA 2021.3 一、File-> New -> Project... 1. 项目类型中选择 Java Enterprise 项目 2. Name：填写自己的项目名称 3. Project template：选择项目的模板，Web application。支持JSP和Servlet的项目 4. Applica…...

编程日记 2023/9/23 11:37:46

源码：TMS FlexCel Studio for .NET 7.19

TMS FlexCel Studio for .NET 是100% 托管代码 Excel 文件操作引擎以及 Excel 和 PDF 报告生成，适用于 .NET、Xamarin.iOS、Xamarin.Android、Xamarin.Mac、Windows Phone 和 Windows Store 功能概述 使用 FlexCel Studio for .NET 创建可动态快速读写 Excel 文件的…...

编程日记 2023/9/23 11:35:44

多输入多输出 | MATLAB实现PSO-BP粒子群优化BP神经网络多输入多输出

多输入多输出 | MATLAB实现PSO-BP粒子群优化BP神经网络多输入多输出 目录 多输入多输出 | MATLAB实现PSO-BP粒子群优化BP神经网络多输入多输出预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 Matlab实现PSO-BP粒子群优化BP神经网络多输入多输出预测 1.data为数据…...

编程日记 2023/9/23 11:34:42

操作系统：系统引导以及虚拟机

1.操作系统引导的过程 ①CPU从一个特定主存地址开始取指令，执行ROM中的引导程序（先进行硬件自检，再开机)②将磁盘的第一块：主引导记录读入内存，执行磁盘引导程序，扫描分区表③从活动分区（又称主…...

编程日记 2023/9/23 11:27:37

AIGC绘本——海马搬家来喽

随着ChatGPT的快速发展，人工智能领域也发生了翻天覆地的变化。今天，我们迎合科技潮流，利用AIGC的强大能力，可以创作很多精彩的作品，比如这样一本名为《海马搬家》的绘本（注：此绘本根据同名儿童故…...

编程日记 2023/9/23 11:25:35

strtok()函数的使用方法

strtok() 函数用于将字符串分割成子字符串&#xff08;标记&#xff09;。它在 C 语言中非常常用&#xff0c;可以通过指定分隔符来拆分原始字符串&#xff0c;并依次返回每个子字符串。 以下是 strtok() 函数的使用方法&#xff1a; #include <stdio.h> #include <…...

编程日记 2023/9/23 11:23:33

Matlab中的handle 类

目录 说明 类属性 方法 公共方法 事件 示例 从 handle 派生类 说明 ​ handle 类是遵守句柄语义的所有类的超类。句柄是引用 handle 类的对象的变量。多个变量可以引用同一个对象。 handle 类是抽象类&#xff0c;这样无法直接创建该类的实例。使用 handle 类派…...

编程日记 2023/9/23 11:20:31

C#，数值计算——Multinormaldev的计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { public class Multinormaldev : Ran { public Cholesky chol { get; set; } null; private int mm { get; set; } private double[] mean { get; set; } private double[,] xvar {…...

编程日记 2023/9/23 11:15:26

软件项目测试用例评审

软件项目测试用例评审是确保测试计划的一部分&#xff08;即测试用例&#xff09;满足项目质量和要求的关键步骤之一。以下是一个通用的软件项目测试用例评审流程&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎…...

编程日记 2023/9/23 11:10:21

图像处理与计算机视觉--第二章-成像与图像表示-8问

图像处理与计算机视觉--第二章-成像与图像表示-8问 1.光谱波长分布及其成像特点各是什么? 光谱波长分布&#xff1a;是指在不同波长范围内的光的强度或能量分布。它通常可以用光谱图来表示&#xff0c;其中横轴是波长&#xff0c;纵轴是光的强度或能量。 成像特点&#xf…...

编程日记 2023/9/23 11:09:20

python中使用多线程批量导入包

问题放到前面&#xff0c;目前发现一个问题&#xff0c;importlib对于c/c编译过来的包&#xff0c;只支持导入最顶层的包&#xff0c;不过也够了。 因为有些项目的依赖太多&#xff0c;所以导致每个文件头部都包含大量import语句&#xff0c;用来导入必要的包&#xff0c;如果量…...

编程日记 2023/9/23 11:07:17

齿轮减速机设备类网站pbootcms模板（PC端+手机端自适应）

齿轮减速机设备类网站pbootcms模板-手机端自适应&#xff0c;优化SEO效果 模板介绍&#xff1a; 这是一款基于PbootCMS内核开发的模板&#xff0c;专为机械设备和加工机械类企业设计。该模板具有简洁简单的页面设计&#xff0c;易于管理&#xff0c;同时还附带测试数据。通过使…...

编程日记 2023/9/23 11:06:17

MySQL报错：this is incompatible with sql_mode=only_full_group_by 解决方法

文章目录 项目场景&#xff1a;原因分析及解决方案&#xff1a;总结&#xff1a; 项目场景&#xff1a; 提示&#xff1a;这里简述项目相关背景&#xff1a; which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_modeonly_f…...

编程日记 2023/9/23 11:05:16

impala常用时间函数，date-＞string-＞timestamp互转

impala 和hive不一样&#xff0c;hive是弱类型&#xff0c;比如int和string在大部分条件下可以比较 比如hive select 11 --结果true或false 但是impala select 11 报错 operands of type TINYINT and STRING are not comparable: 1 1 这样带来的好处是 类型一致结果更…...

编程日记 2023/9/23 11:04:15

无源供电无线测温系统的应用意义

电力系统设备在长期的运行中&#xff0c;往往会产生老化或过热现象&#xff0c;如果没有及时发现和解决&#xff0c;可能会造成严重的火灾事故。由于变电站设备地理位置偏远&#xff0c;对于其维护和监控&#xff0c;管理人员不能做到面面俱到&#xff0c;巡检和维护的难度较大…...

编程日记 2023/9/23 11:02:12

使用 PyTorch 的计算机视觉简介 （1/6）

一、说明 Computer Vision&#xff08;CV&#xff09;是一个研究计算机如何从数字图像和/或视频中获得一定程度的理解的领域。理解这个定义具有相当广泛的含义 - 它可以从能够区分图片上的猫和狗&#xff0c;到更复杂的任务&#xff0c;例如用自然语言描述图像。 二、CV常见的问…...

编程日记 2023/9/23 11:01:11

Qwen3-TTS在心理治疗中的应用：情感化语音陪伴系统

Qwen3-TTS在心理治疗中的应用&#xff1a;情感化语音陪伴系统 1. 引言 想象一下这样的场景&#xff1a;一位正在经历焦虑情绪的用户&#xff0c;深夜无法入睡&#xff0c;需要即时的情感支持。传统的心理咨询需要预约等待&#xff0c;而此刻他们最需要的是一个能够理解、回应…...

编程新知 2026/3/27 10:17:33

Python AI 用例工具部署踩坑实录：Docker镜像体积暴增300%、GPU显存泄漏、模型热加载失败的5个根因与秒级修复方案

第一章&#xff1a;Python AI 用例工具部署的典型失败图谱在真实生产环境中&#xff0c;Python AI 工具链&#xff08;如 LangChain、LlamaIndex、FastAPI 封装的推理服务&#xff09;的部署失败往往并非源于模型能力缺陷&#xff0c;而是由基础设施、依赖冲突与配置漂移引发的…...

编程新知 2026/3/27 9:18:51

探索电池2RC等效电路模型：从参数辨识到SOC估计

电池2RC等效电路模型&#xff0c;最小二乘法参数辩识&#xff0c;电池端电压误差小&#xff0c;扩展卡尔曼估计SOC精度高。 有文档&#xff0c;数据&#xff0c;视频&#xff0c;仿真图。在电池研究领域&#xff0c;准确建模和参数估计对于理解电池行为至关重要。今天咱就唠唠电…...

编程新知 2026/3/27 8:26:31

分享一份2026金三银四Java面试通关宝典！

金三银四快到了&#xff0c;不少人找LZ咨询&#xff0c;问我现在的面试需要提前准备什么&#xff1f;为了造福更多的开发者&#xff0c;也为了让更多的小伙伴通过面试&#xff1b;LZ近期也一直想着怎么才能帮到大家。所以近期在各大渠道整合大厂相关面试题&#xff0c;并结合了…...

编程新知 2026/3/27 7:26:13

FPGA实战：8点FFT运算的Verilog实现与误差优化技巧

FPGA实战&#xff1a;8点FFT运算的Verilog实现与误差优化技巧 在数字信号处理领域&#xff0c;快速傅里叶变换&#xff08;FFT&#xff09;算法是频谱分析的核心工具。对于FPGA开发者而言&#xff0c;掌握FFT的硬件实现不仅能提升系统性能&#xff0c;更能深入理解算法与硬件的…...

编程新知 2026/3/27 6:33:17

从Windows命令行小白到Scoop社区贡献者：我的完整成长指南

从Windows命令行小白到Scoop社区贡献者&#xff1a;我的完整成长指南 【免费下载链接】Scoop A command-line installer for Windows. 项目地址: https://gitcode.com/gh_mirrors/sc/Scoop 想要在Windows系统上快速安装和管理软件&#xff1f;厌倦了繁琐的图形界面安装过…...

编程新知 2026/3/27 5:28:47

3步实现跨次元游戏模组管理：XXMI启动器的多游戏统一解决方案

3步实现跨次元游戏模组管理&#xff1a;XXMI启动器的多游戏统一解决方案 【免费下载链接】XXMI-Launcher Modding platform for GI, HSR, WW and ZZZ 项目地址: https://gitcode.com/gh_mirrors/xx/XXMI-Launcher 还在为《原神》《崩坏&#xff1a;星穹铁道》等多款二次…...

编程新知 2026/3/27 5:14:44

Android NDK开发从入门到实战：解锁应用性能的终极武器

引言 在Android应用开发领域&#xff0c;Java和Kotlin凭借其简洁的语法和强大的框架支持&#xff0c;成为了绝大多数开发者的首选。然而&#xff0c;当面对高性能计算、游戏引擎集成、硬件加速访问或核心算法保护等场景时&#xff0c;纯Java层的实现往往显得力不从心。这时&…...

编程新知 2026/3/27 4:48:02

2026权威评测：盘点毕业论文AIGC免费降重神器

【CSDN 资深算法架构师 / NLP技术专栏 导读】 各位还在发际线边缘挣扎的应届生和硕博党们&#xff0c;到了2026年&#xff0c;如果你的电脑里还装着那种老掉牙的“同义词替换”降重软件&#xff0c;我劝你赶紧停手&#xff01; 最近CSDN社群里哀嚎一片&#xff1a;“知网查重过…...

编程新知 2026/3/27 4:07:40

Skytraq NavIC库：Arduino平台的GNSS驱动与区域增强开发指南

1. Skytraq NavIC 库概述Skytraq NavIC 库是一个面向 Arduino 平台的完整 GNSS 驱动框架&#xff0c;专为基于 Skytraq 芯片组&#xff08;如 SGR-03、SGR-05、SGR-07 系列&#xff09;的高精度定位模块设计。该库不仅全面支持全球主流卫星导航系统&#xff0c;更深度适配印度区…...

编程新知 2026/3/27 2:38:45