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

数据结构入门-14-排序

news 2026/5/15 8:43:40

在这里插入图片描述

一、选择排序

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

ARM PMU性能监控与PMOVSSET_EL0寄存器详解

1. ARM PMU性能监控体系概述在ARMv8/v9架构中&#xff0c;性能监控单元(Performance Monitoring Unit, PMU)是处理器微架构的重要组成部分&#xff0c;它为开发者提供了硬件级别的性能数据采集能力。PMU通过一组可编程的事件计数器和控制寄存器&#xff0c;使系统软件能够精确监…...

编程新知 2026/5/15 8:03:07

树莓派SPI驱动TFT显示屏：从硬件连接到Python图形编程实战

1. 项目概述与核心价值如果你手头有一块闲置的树莓派&#xff0c;想给它配个小屏幕做个状态监控器、迷你信息站&#xff0c;或者DIY一个便携游戏机&#xff0c;那么连接一块TFT显示屏几乎是必经之路。但当你真正动手时&#xff0c;可能会被一堆引脚、SPI、驱动芯片这些术语搞得…...

编程新知 2026/5/15 7:29:45

APDS9999三合一传感器实战：从硬件解析到代码应用

1. 项目概述&#xff1a;为什么选择APDS9999这款三合一传感器&#xff1f;在嵌入式项目里&#xff0c;传感器选型常常是个让人头疼的问题。你想做个能根据环境光自动调节亮度的智能灯&#xff0c;需要一个光照传感器&#xff1b;想做个检测物体靠近的感应装置&#xff0c;需要一…...

编程新知 2026/5/15 7:27:45

【独家拆解】Sora 2正式版底层架构升级：从DiT-XL到时空联合注意力v3.2，性能提升217%的关键证据

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Sora 2正式版发布背景与核心定位 OpenAI 于2024年第三季度正式发布 Sora 2&#xff0c;标志着视频生成模型从实验性原型迈入工业级部署新阶段。此次发布并非简单迭代&#xff0c;而是基于对数百万小时真…...

编程新知 2026/5/15 7:23:10

GelSight 视触觉3D显微系统 4.4 软件版本上线，粗糙度测量维度全面拓展

近日&#xff0c;GelSight推出V4.4软件版本&#xff0c;同步适配 GelSight视触觉3D显微系统全系列产品&#xff0c;围绕3D表面形貌检测、表面粗糙度测量、无损弹性3D成像核心能力优化&#xff0c;为材料科学、精密制造、航空航天、增材制造等领域科研人员提供非接触式检测方案。…...

编程新知 2026/5/15 6:20:53

构建本地化JavaScript智能补全引擎：从AST解析到上下文感知推荐

1. 项目概述&#xff1a;一个为现代编辑器而生的JavaScript智能引擎如果你是一名前端开发者&#xff0c;或者经常与代码编辑器打交道&#xff0c;那么你一定对“代码补全”、“智能提示”这些功能又爱又恨。爱的是它们能极大提升编码效率&#xff0c;恨的是它们有时不够精准&am…...

编程新知 2026/5/15 5:35:53

WordPress至PageAdmin CMS跨平台迁移技术指南：应对环境约束的系统化过渡方案

对于许多依赖WordPress的国内站长而言&#xff0c;核心痛点往往不在于WordPress本身的功能或性能——作为全球使用率最高的CMS&#xff0c;其生态成熟度毋庸置疑。真正的挑战来自外部环境&#xff1a;WordPress核心更新、插件商店及主题库的服务器位于海外&#xff0c;频繁遭遇…...

编程新知 2026/5/15 3:43:44

猫抓cat-catch浏览器扩展：专业级资源嗅探与下载解决方案

猫抓cat-catch浏览器扩展&#xff1a;专业级资源嗅探与下载解决方案 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 你是否曾遇到这样的情况&#…...

编程新知 2026/5/15 3:37:28

AI工程化实战：从模型到服务的全链路部署与优化指南

1. 项目概述&#xff1a;一个面向AI应用开发的综合框架最近在开源社区里&#xff0c;Sunpeak-AI/sunpeak 这个项目引起了我的注意。它不是一个单一的模型或工具&#xff0c;而是一个旨在为AI应用开发提供“一站式”解决方案的框架。简单来说&#xff0c;你可以把它理解为一个工…...

编程新知 2026/5/15 3:33:21

Adafruit Feather 32u4 FONA：基于Arduino与2G GSM的物联网远程通信开发板实战指南

1. 项目概述与核心价值如果你正在寻找一款能让你快速将物联网设备“扔”到世界任何角落&#xff0c;并且还能打个电话、发条短信的开发板&#xff0c;那么Adafruit Feather 32u4 FONA绝对值得你花时间研究。我最初接触它&#xff0c;是为了一个野外环境监测项目&#xff0c;需要…...

编程新知 2026/5/15 3:33:20