排序(基数,堆,归并)

基数排序

定义0-9十个桶,先排序个数,在排序十位,依次向下(桶就是二维数组)

按照个位先排一次

个位已经有序了,桶内遵循先进先出

没有十位放到0里

取出

百位

这样排序就完成了。放进取出几次,取决于最大数一共有几位。

时间复杂度

按照个位:挨个遍历,挨个取出----O(n)

最大数k位 复杂度O(kn)

堆排序

1.利用完全二叉树构建大顶堆

2.堆顶元素和堆底元素进行交换,除堆底元素,剩余元素继续构建大顶堆。

3.不断重复2,直到排序完成

完全二叉树:要求数据必须从上到下,从左到右的顺序

这就是一个完全二叉树

什么是大顶堆:父节点的值大于或等于其左右节点的值

堆顶元素:arr[0] 堆底元素 arr[arr.length-1]

0的左右孩子 1 2 1的左右孩子 3 4 2的左右孩子 5 6

所有得出结论 arr[i]的左孩子是 arr[2i+1] arr[i]的右孩子是 arr[2i+2] arr[i]的父节点是 arr[(i-1)/2]

arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]

如何构建大顶堆???

从后往前检测每一个节点是否符合大顶堆,符合检测前一个,不符合对其进行维护,让其符合大顶堆

1.定义parent游标指向该节点

2.定义parent的左孩子 child=2*parent+1,判断有没有左孩子,没有则符合大顶堆,如果有左孩子,判断有没有右孩子。有右孩子,左右孩子进行比较,child指向左右孩子中最大的值

3.父子节点进行比较

4.父节点大,符合大顶堆,继续向前检测

5.子节点的值大,父子节点进行交换,交换完成,parent指向child,child指向左右孩子最大值,继续比较parent和child,直到parent的值大,或者child为空

6.重复以上操作

形成大顶堆,堆顶堆底交换,7不参与构建了

然后继续形成大顶堆,继续交换就好了

时间复杂度

1层 1个数据

2层 2

3层 4

4层 8

k层 2^(k-1)

2^k -1 =n

k=log2n

维护一个节点的时间复杂度O(logn)

维护N个节点 O(Nlogn)

初始化一个堆时间复杂度O(n)

整个堆排序时间复杂度 O(nlogn)

归并排序

合并有序序列

s1 s2不断比较谁小谁进去

归并排序: 先拆分在合并

拆分:从中间位置拆开,数据分左右两部分,继续拆分,直到拆成一个一个停止

然后在比较合并

时间复杂度:

第一次拆分 2个数组

2 4

3 8

k x

x=2^k k=log2x

合并 合并一次会把数据都遍历一边

时间复杂度 O(logn)*O(n)=O(nlogn)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/401305.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Flink Checkpoint expired before completing解决方法

在Flink消费Kafka日志的时候出现了这样的一则报错, JobManager报错如下: 2024-03-07 15:21:12,500 [Checkpoint Timer] WARN org.apache.flink.runtime.checkpoint.CheckpointFailureManager [] - Failed to trigger or complete checkpoint 181 for …

Python酷库之旅-第三方库Pandas(082)

目录 一、用法精讲 341、pandas.Series.str.startswith方法 341-1、语法 341-2、参数 341-3、功能 341-4、返回值 341-5、说明 341-6、用法 341-6-1、数据准备 341-6-2、代码示例 341-6-3、结果输出 342、pandas.Series.str.strip方法 342-1、语法 342-2、参数 …

bug的常见排查和分析思路以及相关的原因分类

作为开发人员,经常会收到来自用户和QA,领导反馈的各种问题。 为了快速问题,我们有时需要站在更高的角度,更全面的看待问题。才能更快锁定问题。 具体的bug还需要结合企业实际业务情况,相关的框架,依赖库&…

PHP项目任务系统小程序源码

🚀解锁高效新境界!我的项目任务系统大揭秘🔍 🌟 段落一:引言 - 为什么需要项目任务系统? Hey小伙伴们!你是否曾为了杂乱的待办事项焦头烂额?🤯 或是项目截止日逼近&…

QT、C++简单界面设计

#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {---------------------窗口设置----------------------this->setWindowTitle("南城贤子摄影工作室");//设置窗口标题this->setWindowIcon(QIcon("d:\\Pictures\\C…

PUMA论文阅读

PUMA: Efficient Continual Graph Learning with Graph Condensation PUMA:通过图压缩进行高效的连续图学习 ABSTRACT 在处理流图时,现有的图表示学习模型会遇到灾难性的遗忘问题,当使用新传入的图进行学习时,先前学习的这些模…

c语言中比较特殊的输入格式

目录 一.%[ ] 格式说明符 1.基本用法 (1)读取字母字符: (2)读取数字字符: (3)读取所有字符直到遇到空格: (4)读取直到换行符: 2.使用范围和组合: 3.^ 取反操作 4.注意事项 (1). 字符范围的正确表示 (2). 避免字符集中的特殊字符冲突 (3).避免空字符集 (4). 输入长…

构建高效外贸电商系统的技术探索与源码开发

在当今全球化的经济浪潮中,外贸电商作为连接国内外市场的桥梁,其重要性日益凸显。一个高效、稳定、功能全面的外贸电商系统,不仅能够助力企业突破地域限制,拓宽销售渠道,还能提升客户体验,增强品牌竞争力。…

Wireshark过滤规则

一、按IP地址过滤 1、查看源IP为 xx 的包 ip.srcIP地址 例如:ip.src172.18.10.56 2、查看目标IP为 xx 的包 ip.dstIP地址 例如:ip.dst172.16.76.251 3、查看源或目标IP为 xx 的包 ip.addrIP地址 例如:ip.addr172.18.10.56 二、按MAC地…

数学建模--浅谈多波束测线问题

目录 1.问题说明 2.问题分析 3.代码分析 1.问题说明 这个是国赛的真题,我们这个里面只是浅谈,就是对于这个里面运用的过程仿真的思路进行说明,这个探测的波束问题实际上也是一个简单的过程仿真问题,也是需要去进行作图的&#…

【中等】 猿人学web第一届 第5题 js混淆-乱码增强

文章目录 请求流程请求参数cookie信息 加密参数定位Hook CookieAST 还原混淆代码解密函数还原字符串还原数组引用还原浏览器内置对象 / 变量值引用还原逗号表达式还原 unicode, 16进制数值字符串相加AST 解混淆完整代码 加密参数还原cookie m字段m字段坑点 cookie RM4hZBv0dDon…

什么是云原生?(二)

1. 云原生的定义 云原生指构建和运行应用以充分利用通过云技术交付模式交付的分布式计算。云原生应用旨在充分利用云技术平台特有的可扩展性、弹性和灵活性优势。 根据云原生计算基金会 (CNCF) 的定义,云原生技术可帮助企业在公有云、私有云和混合云环境中构建和…

Unity Render Streaming项目实践经验

UnityRenderStreaming项目 项目github地址见上,我使用项目的3.1.0-exp.7版本、Unity 2023.1.0版本、windows11运行。 1下载项目包 2在Unity Hub中打开RenderStreaming~文件夹 3在package manager中导入com.unity.renderstreaming package 因为已经下载过了就选择install pa…

Word中加载Mathtype后粘贴复制快捷键(Ctrl+C/V)不能使用

操作环境 windows 11操作系统 word版本2021 mathtype版本7.4 这个问题只出现在word中,在excel和ppt中都不存在这个问题,而且之前在另一台电脑中使用word2016版本并没有这种问题的,然后网上搜了一下有不少人有这种问题,word直接取…

Docker Containerd初体验

Docker Containerd概述 ​ Containerd是一个开源的容器运行时,它提供了一种标准化的方式来管理容器的生命周期。该项目最初是由Docker开发团队创建的,并在后来成为了一个独立的项目,被纳入了Cloud Native Computing Foundation(C…

Taos 常用命令工作笔记(二)

最近测试创建一个涛思的数据库和一堆表进行测试,通过json配置文件配置字段的类型、名称等,程序通过解析json文件的配置,动态创建数据库的表。 其中表字段为驼峰结构的规则命名,创建表也是成功的,插入的测试数据也是成功…

html页面缩放自适应

html页面缩放自适应 一、为什么页面要进行缩放自适应 在我们一般web端进行页面拼接完成后,在web端的显示正常(毕竟我们是按照web端进行页面拼接完成的),那么要是用其他设备打开呢,比如手机或者平板,这时候…

【Datawhale AI夏令营第四期】魔搭-AIGC方向 Task02笔记 Scepter工具箱, 精读BaseLine代码

【Datawhale AI夏令营第四期】魔搭-AIGC方向 Task02笔记 Task02学习任务: https://linklearner.com/activity/14/10/32 传送门 我们继续看网课,并且在Kimi.AI的帮助下读一下BaseLine示例代码。 网课链接:https://space.bilibili.com/1069874…

WebService基础学习

一、XML回顾 二、HTTP协议回顾 三、复习准备 四、关于Web Service的几个问题 五、Web Service中的几个重要术语 六、开发webservice 七、WebService面试题

比char类型小的变量——位段

目录 开头1.什么是位段?2.位段的优缺点优点缺点 3.位段的实际应用…… 结尾 开头 大家好,我叫这是我58。在今天,我们将要介绍一个既比char类型小,又只用于结构体的一种东西——位段。 1.什么是位段? 位段,就是一种比char类型…