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

数据结构入门-14-排序

news 2025/7/2 11:21:32

在这里插入图片描述

一、选择排序

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

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

编程新知 2025/6/25 2:24:39

练习（含atoi的模拟实现,自定义类型等练习）

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

编程新知 2025/6/28 14:02:39

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

编程新知 2025/6/23 6:42:53

C++.OpenGL （10/64）基础光照（Basic Lighting）

基础光照（Basic Lighting） 冯氏光照模型（Phong Lighting Model） #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

编程新知 2025/6/25 15:26:59

在Mathematica中实现Newton-Raphson迭代的收敛时间算法（一般三次多项式）

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

编程新知 2025/6/21 10:39:07

MinIO Docker 部署：仅开放一个端口

MinIO Docker 部署：仅开放一个端口 在实际的服务器部署中，出于安全和管理的考虑，我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务，支持 Docker 部署，但默认情况下它需要两个端口：一个是 API 端口（用于存储和访问数据），另一个是控制台端口（用于管理界面…...

编程新知 2025/6/21 15:09:46

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

编程新知 2025/6/22 12:22:35

负载均衡器》》LVS、Nginx、HAproxy 区别

虚拟主机 先4&#xff0c;后7...

编程新知 2025/6/30 10:08:15

ArcGIS Pro+ArcGIS给你的地图加上北回归线！

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...

编程新知 2025/6/30 10:20:16

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

编程新知 2025/7/1 18:20:47