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

常见的排序算法,复杂度

  • 稳定 / 非稳定排序:两个相等的数 排序前后 相对位置不变。
  • 插入排序(希尔排序):
    • 每一趟将一个待排序记录,按其关键字的大小插入到已排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。稳定,O(n),O(1)。
    • 把记录按下标增量(模)分组,对每组进行直接插入排序,每次排序后减小增量,当增量减至 1 时排序完毕。不稳定,不知道(有个实验结论),O(1)。
  • 冒泡排序:
    • 比较相邻的元素,如果第一个比第二个大就进行交换,对每一对相邻元素做同样的工作。稳定,O(n),O(1)。
  • 选择排序:
    • 每次在未排序序列中找到最小元素,和未排序序列的第一个元素交换位置,再在剩余未排序序列中重复该操作,直到所有元素排序完毕。不稳定,O(n),O(1)。
  • 桶排序:
    • 将数组分到有限数量的桶里(比如按照十进制最高位,分到10个桶里),每个桶分别排序(可能使用别的排序算法,也可能递归桶排序),然后把排序好的桶连接起来。
    • 稳定。桶数量 = 数据量时,O(N),O(N)。桶数量 = 2,完全递归桶排序,O(NlogN),O(N)。
  • 归并排序:
    • 将待排序序列分成两部分,先对两部分 分别递归排序,然后进行合并。稳定,O(nlogn),O(n)。
  • 堆排序:
    • 堆是一种完全二叉树,最大值堆:子节点均小于父节点,最小值堆:子节点均大于父节点。
    • 插入:放在完全二叉树最后一点,一直往上升。
    • 删除:取出根节点,最后一点升顶,往下降。
    • 不稳定,O(nlogn),O(1)(树状数组)。
  • 快速排序:
    • 随机选择一个基准元素,通过一趟遍历 将要排序的数据分割成两部分,一部分全部小于等于基准元素,一部分全部大于等于基准元素,继续对两部分递归快排。不稳定,O(nlogn),O(1)。
    • 最优:每一次选基准元素都恰好选到中位数,⼆叉树的层数(logn)即为递归需要进⾏的次数,并且每轮递归结束时,都将⼆叉树遍历了⼀遍(n),O(nlogn)。
    • 最差:数组完全倒序,每次都选到最大的作基准,O(n^2)。

相关文章:

常见的排序算法,复杂度

稳定 / 非稳定排序:两个相等的数 排序前后 相对位置不变。插入排序(希尔排序): 每一趟将一个待排序记录,按其关键字的大小插入到已排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。稳定&…...

鸿蒙特色物联网实训室

一、 引言 在当今这个万物皆可连网的时代,物联网(IoT)正以前所未有的速度改变着我们的生活和工作方式。它如同一座桥梁,将实体世界与虚拟空间紧密相连,让数据成为驱动决策和创新的关键力量。随着物联网技术的不断成熟…...

JVM垃圾回收-----垃圾分类

一、垃圾分类定义 垃圾分类是JVM垃圾分类中的第一步,这一步将堆中的对象分为存活对象和垃圾对象两类。 在垃圾分类阶段,JVM会从一组根对象开始,通过对象之间的引用关系,遍历所有的对象,并将所有存活的对象进行标记。…...

前端基础之JavaScript学习——变量、数据类型、类型转换

大家好,我是来自CSDN的博主PleaSure乐事,今天我们开始有关JS的学习,希望有所帮助并巩固有关前端的知识。 我使用的编译器为vscode,浏览器使用为谷歌浏览器,使用webstorm或其他环境效果几乎一样,使用系统自…...

SQL常用数据过滤---IN操作符

在SQL中,IN操作符常用于过滤数据,允许在WHERE子句中指定多个可能的值。如果列中的值匹配IN操作符后面括号中的任何一个值,那么该行就会被选中。 以下是使用IN操作符的基本语法: SELECT column1, column2, ... FROM table_name WH…...

HDFS和FDFS

HDFS(Hadoop Distributed File System)和FDFS(FastDFS)是两种不同的分布式文件系统,它们各自有不同的设计目标和使用场景。以下是对它们的详细介绍: HDFS(Hadoop Distributed File System&…...

Flutter对接FlutterBugly 报错Zone mismatch

在Flutter对接FutterBlugy时报如下错误: Unhandled Exception: Zone mismatch. E/flutter ( 1292): The Flutter bindings were initialized in a different zone than is now being used. This will likely cause confusion and bugs...

Docker缩小镜像体积与搭建LNMP架构

镜像加速地址 {"registry-mirrors": ["https://docker.m.daocloud.io","https://docker.1panel.live"] } daemon.json 配置文件里面 bip 配置项中可以配置docker 的网段 {"graph": "/data/docker", #数据目录&#xff0…...

六边形动态特效404单页HTML源码

源码介绍 动态悬浮的六边形,旁边404文字以及跳转按钮,整体看着像科技二次元画风,页面简约美观,可以做网站错误页或者丢失页面,将下面的代码放到空白的HTML里面,然后上传到服务器里面,设置好重定向即可 效果预览 完整源码 <!DOCTYPE html> <html><head…...

BGP路径属性

路径属性分类 1. 公认属性&#xff08;所有 BGP 路由器都能识别&#xff09; (1) 公认必遵 a&#xff09; AS path b&#xff09;Origin c&#xff09; Next hop (2) 公认任意 a&#xff09; local preference b&#xff09;atomic aggregate 2. 可选属性&#xff08;…...

从零开始学量化~Ptrade使用教程(六)——盘后定价交易、港股通与债券通用质押式回购

盘后固定价交易 实现科创板、创业板的盘后固定价交易&#xff0c;界面如下显示&#xff1a; 交易 输入科创板或创业板代码&#xff0c;选择委托方向&#xff0c;输入委托价格、委托数量&#xff0c;点击“买入”或“卖出”按钮进行委托。可出现一个委托提示框提示是否继续委托操…...

Docker 三剑客

文章目录 Docker 三剑客1. Docker Engine功能与特点&#xff1a;工作原理&#xff1a;示例命令&#xff1a; 2. Docker Compose功能与特点&#xff1a;工作原理&#xff1a;示例文件 (docker-compose.yml)&#xff1a;示例命令&#xff1a; 3. Docker Swarm功能与特点&#xff…...

每天一个数据分析题(四百三十一)- 卡方检验

在列联表分析中&#xff0c;下列不能用卡方检验的是&#xff08;&#xff09; A. 多个构成的比较 B. 多个率的比较 C. 多个均值的比较 D. 以上都不是 数据分析认证考试介绍&#xff1a;点击进入 题目来源于CDA模拟题库 点击此处获取答案 数据分析专项练习题库 内容涵盖…...

Flowable-流程图标与流程演示

BPMN 2.0是业务流程建模符号2.0的缩写。它由Business Process Management Initiative这个非营利协会创建并不断发展。作为一种标识&#xff0c;BPMN 2.0是使用一些符号来明确业务流程设计流程图的一整套符号规范&#xff0c;它能增进业务建模时的沟通效率。目前BPMN2.0是最新的…...

MyBatis源码中的设计模式2

组合模式的应用 组合模式介绍 组合模式(Composite Pattern) 的定义是&#xff1a;将对象组合成树形结构以表示整体和部分的层次结构。组合模式可以让用户统一对待单个对象和对象的组合。 比如&#xff1a;Windows操作系统中的目录结构&#xff0c;通过tree命令实现树形结构展…...

AI发展中的伦理挑战与应对策略

AI发展中的伦理挑战与应对策略 人工智能&#xff08;AI&#xff09;的快速发展在为社会带来许多便利和创新的同时&#xff0c;也带来了诸多伦理挑战。这些挑战主要集中在数据隐私侵犯、信息茧房的制造、歧视性算法、深度伪造技术等方面。针对这些问题&#xff0c;需要从多个层…...

基于用户非兴趣/非偏好/非习惯的推荐

基于用户非兴趣、非偏好、非习惯的推荐是一种个性化推荐技术&#xff0c;旨在为用户提供与其日常行为和兴趣模式不同的推荐内容。这种推荐方法的目的是打破用户的信息过滤和习惯&#xff0c;发现新的、潜在的兴趣点&#xff0c;从而提供更广泛和多样化的推荐结果。 通过收集和分…...

Abaqus基于CT断层扫描的三维重建插件CT2Model 3D

插件介绍 AbyssFish CT2Model 3D V1.0 插件可将采用X射线等方法获取的计算机断层扫描&#xff08;CT&#xff09;图像在Abaqus有限元软件内进行三维重建&#xff0c;进而高效获取可供模拟分析的有限元模型。插件可用于医学影像三维重构、混凝土细观三维重建、岩心数字化等领域…...

Mindspore框架CycleGAN模型实现图像风格迁移|(三)损失函数计算

Mindspore框架&#xff1a;CycleGAN模型实现图像风格迁移算法 Mindspore框架CycleGAN模型实现图像风格迁移|&#xff08;一&#xff09;CycleGAN神经网络模型构建 Mindspore框架CycleGAN模型实现图像风格迁移|&#xff08;二&#xff09;实例数据集&#xff08;苹果2橘子&…...

ENSP中VLAN的设置

VLAN的详细介绍 VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是一种将一个物理的局域网在逻辑上划分成多个广播域的技术。 以下是关于 VLAN 的一些详细介绍&#xff1a; 一、基本概念 1. 作用&#xff1a; - 隔离广播域&#xff1a…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

【Ftrace 专栏】Ftrace 参考博文

ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...