软考29-上午题-排序
一、排序的基本概念
1-1、稳定性
稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后,次序不变,则是稳定的。
1-2、归位
每一趟排序能确定一个元素的最终位置。
1-3、内部排序
排序记录全部存放在内存中进行排序的过程。
1-4、外部排序
待排序记录的数量很大,以至于内存不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
1-5、排序小结(要背)

比较最好时间复杂度,会发现,当待排序的序列基本有序的话,适合采用:
- 直接插入排序
- 希尔排序
- 冒泡排序
二、直接插入排序

稳定的
不归位

三、希尔排序
直接插入排序的改进。
基本思想:现将整个待排记录序列分割成若干子序列,然后分别进行直接插入排序;待整个序列中的记录基本有序的时候,再对全体记录进行一次直接插入排序。
示例:


不稳定
不归位
四、真题1
真题1:

真题2:
真题3:

真题4:

五、简单选择排序
算法思想:从待排数组中找到最小值,再将最小值与已排好序的数组后一位进行交换。

归位
不稳定

六、堆排序(简单了解)
示例:


此时,根元素80是最大的元素,将根元素80和队列最后一个元素10交换,并将80脱离当前序列(归位),此时,新的二叉树不满足大顶堆的规则,则继续调整。
每次调整完得到的根节点都是当前序列的最大元素!!!

归位
不稳定


七、真题2
真题1:

真题2:

八、冒泡排序
基本思想:相邻两个元素,俩俩交换。


稳定
归位
九、快速排序
快速排序首先选择了一个基准值,然后分别选择两个指针在数组中一个找大,一个找小,然后进行交换。
通过一趟排序将待排序的记录以基准值为分界,分为独立的两个部分,称为前半区和后半区;前半区均小于基准值,后半区均大于基准值。
然后再分别对这两个部分在进行快速排序,从而使得整个序列有序。
分治:分而治之。
归位
不稳定!!!

纠错:空间时间复杂度是:O(log2n);

十、真题2
真题1:

真题2:

真题3:

真题4:

十一、归并排序

示例:



设计方法:分治法
不归并
稳定

11-1、真题
真题1:

真题2:
真题3:

真题4:

真题5:

真题6:

十二、排序小结
12-1、简单排序
1、直接插入排序(稳定)
2、冒泡排序(稳定)
3、简单选择排序(不稳定)
时间复杂度都是:O(n^2)
空间复杂度:O(1)
12-2、希尔排序(不稳定)
时间复杂度:O(n^1.3)
空间复杂度:O(1)
12-3、快速排序(不稳定)
分治思想
时间复杂度:O(nlog2n)——性能最好
空间时间复杂度:O(log2n)
但是,当待排序列基本有序的时候,是最坏的情况,时间复杂度退化为:O(n^2)
12-4、堆排序(不稳定)
时间复杂度:O(nlog2n)
空间时间复杂度:O(1)
12-5、归并排序(稳定)
俩俩归并,n/2向上取整
整个归并排序,需要进行log2n趟(向上取整)
空间复杂度:O(n)
时间复杂度:O(nlogn)
12-6、小结-稳定的排序
- 直接插入排序;
- 冒泡排序
- 归并排序
12-7、真题
真题1:

真题2:

真题3:

直接插入排序:局部有序
冒泡:每一趟排序,都将最大的泡泡在最后的位置。
相关文章:
软考29-上午题-排序
一、排序的基本概念 1-1、稳定性 稳定性指的是相同的数据所在的位置经过排序后是否发生变化。若是排序后,次序不变,则是稳定的。 1-2、归位 每一趟排序能确定一个元素的最终位置。 1-3、内部排序 排序记录全部存放在内存中进行排序的过程。 1-4、外部…...
【详细流程】vue+Element UI项目中使用echarts绘制圆环图 折线图 饼图 柱状图
vueElement UI项目中数据分析功能需要用到圆环图 折线图 饼图 柱状图等,可视化图形分析 安装流程及示例 1.安装依赖 npm install echarts --save2.在main.js中引入并挂载echarts import echarts from echarts Vue.prototype.$echarts echarts3.在需要使用echart…...
Unity之XR Interaction Toolkit如何在VR中实现一个可以拖拽的UI
前言 普通的VR项目中,我们常见的UI都是一个3D的UI,放置在场景中的某个位置,方便我们使用射线点击。但是为了更好的体验,我们可能会有跟随头显的UI,或者可拖拽的UI,这样更方便用户去操作。 所以我们今天的需求就是:如何基于XR Interaction Toolkit 插件 在VR中使用手柄射…...
开源项目热度榜单
题目描述 某个开源社区希望将最近热度比较高的开源项目出一个榜单,推荐给社区里面的开发者。对于每个开源项目,开发者可以进行关注(watch)、收藏(star)、fork、提issue、提交合并请求(MR)等。 数据库里面统计了每个开源项目关注、收藏、fork、issue、M…...
Ubuntu系统搭建HadSky论坛并结合内网穿透实现无公网ip远程访问
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
gowin GW1N4 LED
基于上已篇文章基础上增加LED闪烁的功能 《gowin GW1N4 OSC IP 使用》 gowin GW1N4 OSC IP 使用-CSDN博客 https://blog.csdn.net/wzy15965343032/article/details/136172184?spm1001.2014.3001.5502 代码: module osc_test(input rst_n,output test_clk,output …...
Linux ipvlan详解(l2、l3、l3s和bridge、private和vepa模式)
Linux ipvlan详解,测试l2、l3、l3s和bridge、private和vepa模式。 最近在看Docker的网络,看到关于ipvlan网络的介绍。查阅了相关资料,记录如下。 参考 1.图解几个与Linux网络虚拟化相关的虚拟网卡-VETH/MACVLAN/MACVTAP/IPVLAN 2.IPVlan 详…...
理解并实现OpenCV中的图像平滑技术
导读 图像模糊(也称为图像平滑)是计算机视觉和图像处理中的基本操作之一。模糊图像通常是噪声减少、边缘检测和特征提取等应用的第一步。在本博客中,我们将重点介绍如何使用Python中的OpenCV库应用多种模糊技术。 理论概述: 基本…...
ChatGPT高效提问—prompt实践(白领助手)
ChatGPT高效提问—prompt实践(白领助手) 随着社会的不断发展,白领的比例越来越高。白领的工作通常较为繁忙,需要管理复杂的项目。工作量大、要求高、任务紧急,时间分配不当部分可能导致工作效率低下,任…...
Code Composer Studio (CCS) - Comment (注释)
Code Composer Studio [CCS] - Comment [注释] References Add Block Comment: 选中几行代码 -> 鼠标右键 -> Source -> Add Block Comment shortcut key: Ctrl Shift / Remove Block Comment: 选中几行代码->鼠标右键->Source->Remove Block Comment s…...
springboot/ssm校园菜鸟驿站管理系统Java校园快递取件管理系统
springboot/ssm校园菜鸟驿站管理系统Java校园快递取件管理系统 开发语言:Java 框架:springboot(可改ssm) vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:mysql 5.…...
【Mybatis】TypeHandler使用
引言 在使用MyBatis进行项目开发时,我们经常会遇到Java类型与数据库类型不匹配的情况。为了解决这一问题,MyBatis提供了一个强大的机制——TypeHandler。TypeHandler是MyBatis中一个用于处理Java类型和数据库类型转换的组件,它在MyBatis进行…...
[计算机网络]---网络编程套接字
前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃 如果觉的博主的文章还不错的话,还请点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、基础知识…...
分布式文件系统 SpringBoot+FastDFS+Vue.js【二】
分布式文件系统 SpringBootFastDFSVue.js【二】 六、实现上传功能并展示数据6.1.创建数据库6.2.创建spring boot项目fastDFS-java6.3.引入依赖6.3.fastdfs-client配置文件6.4.跨域配置GlobalCrosConfig.java6.5.创建模型--实体类6.5.1.FastDfsFile.java6.5.2.FastDfsFileType.j…...
开源软件:推动软件行业繁荣的力量
文章目录 📑引言开源软件的优势分析开放性与透明度低成本与灵活性创新与协作 开源软件对软件行业的影响推动技术创新和进步促进软件行业的合作与交流培养人才和提高技能促进软件行业的可持续发展 结语 📑引言 随着信息技术的飞速发展,软件已经…...
[杂记]mmdetection3.x中的数据流与基本流程详解(数据集读取, 数据增强, 训练)
之前跑了一下mmdetection 3.x自带的一些算法, 但是具体的代码细节总是看了就忘, 所以想做一些笔记, 方便初学者参考. 其实比较不能忍的是, 官网的文档还是空的… 这次想写其中的数据流是如何运作的, 包括从读取数据集的样本与真值, 到数据增强, 再到模型的forward当中. 0. MMDe…...
阿里云香港轻量应用服务器怎么样,建站速度快吗?
阿里云香港服务器中国香港数据中心网络线路类型BGP多线精品,中国电信CN2高速网络高质量、大规格BGP带宽,运营商精品公网直连中国内地,时延更低,优化海外回中国内地流量的公网线路,可以提高国际业务访问质量。阿里云服务…...
事务及在SpringBoot项目中使用的两种方式
1.事务简介 事务(transaction)是访问并可能操作各种数据项的一个数据库操作序列,这些操作要么全部执行,要么全部不执行,是一个不可分割的工作单位。 事物的四大特性: 原子性(Atomicity)…...
stm32--笔记
一、引脚与变量 二、STM32时钟 [STM32-时钟系统详解_stm32时钟_KevinFlyn的博客-CSDN博客] 三、定时器中断实验 1、定时器中断实验 stm32关于通用定时器的周期、频率计算公式_stm32tim频率计算_胶囊咖啡的博客-CSDN博客 【STM32】通用…...
2024前端面试准备之CSS篇(二)
全文链接 1. 什么是伪类和伪元素 伪类(Pseudo-class): 伪类是选择器的一种,用于选择特定状态或条件下的元素。它们以冒号(:)开头,用于向选择器添加额外的特定条件。例如,:hover伪类用于选择鼠标悬停在元素上的状态,:nth-child(n)伪类用于选择父元素下的第n个子元素等。…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
