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

数据结构入门-14-排序

news 2025/10/15 22:59:11

在这里插入图片描述

一、选择排序

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

UE5 学习系列（三）创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

编程新知 2025/10/12 5:46:53

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

编程新知 2025/10/5 8:09:39

多种风格导航菜单 HTML 实现（附源码）

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

编程新知 2025/9/28 3:32:05

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

编程新知 2025/10/6 22:42:00

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

编程新知 2025/9/30 3:57:32

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

编程新知 2025/9/28 3:34:24

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

编程新知 2025/7/9 0:26:24

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

编程新知 2025/10/11 22:24:22

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

编程新知 2025/9/30 23:36:37

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

编程新知 2025/10/8 13:18:42