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

数据结构入门-14-排序

news 2026/2/7 3:16:27

在这里插入图片描述

一、选择排序

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

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

编程新知 2025/12/3 20:14:32

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

编程新知 2026/1/15 4:39:38

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

编程新知 2026/1/26 21:56:38

MySQL 8.0 OCP 英文题库解析（十三）

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

编程新知 2026/1/31 7:25:57

UR 协作机器人「三剑客」：精密轻量担当（UR7e）、全能协作主力（UR12e）、重型任务专家（UR15）

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

编程新知 2026/2/2 2:47:37

Python Ovito统计金刚石结构数量

大家好，我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构，但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法，可以持续统计各步的金刚石结构，具体代码如下： from ovito…...

编程新知 2026/1/26 5:39:08

虚拟电厂发展三大趋势：市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

编程新知 2025/12/20 18:09:59

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

编程新知 2026/1/31 8:45:21

【Kafka】Kafka从入门到实战：构建高吞吐量分布式消息系统

Kafka从入门到实战：构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台，最初由LinkedIn开发，后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理，能够处理来自多个生产者的海量数据，并将这些数据实时传递给消费者。 Kafka核心特…...

编程新知 2025/7/18 7:59:36

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

编程新知 2026/1/26 17:05:57