排序算法问题
给你一个整数数组 nums,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1] 输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0] 输出:[0,0,1,1,2,5]
代码如下:
1.插入排序(简单插入排序、直接插入排序)

//算法思想;从当前位置开始,从后往前找比数字小的,找到后插入到这个小的数字后面
//再找的过程中,如果发现一个比当前数字大,同时将这个数字往后移动
//时间复杂度:O(n^2) 空间复杂度O(1) 稳定性:稳定,没有跳跃式的交换数据
//直接插入排序的特点:越有序越快;完全有序能达到O(n);
class Solution {
public:void InsertSort(vector<int>& nums,int n){for(int i=0;i<n;i++) {int temp = nums[i];//记录未排序数组的下标int j = i-1;//记录已经排序数组的下标while(j >= 0 && nums[j] >temp) {nums[j+1] = nums[j];//当已经排序好的数组数字大于未排序的数组数字,将已经排序好的数字向后移一个j--;}nums[j+1] = temp;//如果未排序的数组数字大于已经排序好的数字,直接插入到排序好的数字后面}}vector<int> sortArray(vector<int>& nums) {int n=nums.size();InsertSort(nums,n);return nums;}
};
2.希尔排序

//直接插入排序越有序越快是希尔排序的一个理论基础
//算法描述:1.间隔式的分组 2.利用直接插入排序让组内有序 3.缩小分组再次排序 4.再次调用直接插入排序 ...直到缩为一组完全有序
//时间复杂度:O(n^1.3-n^1.5) 空间复杂度:O(1) 稳定性:不稳定
class Solution {
public:void ShellSort(vector<int>& nums,int n){int gap=n;while(gap>1)//间隔式分组,每一组利用直接插入排序,让组内有序{gap/=2;//每次分组都在上一组的基础上折半for(int i=gap;i<n;i++) {int temp = nums[i];int j = i-gap;while(j >= 0 && nums[j] >temp) {nums[j+gap] = nums[j];j-=gap;}nums[j+gap] = temp;}}}vector<int> sortArray(vector<int>& nums) {int n=nums.size();ShellSort(nums,n);return nums;}
};
3.冒泡排序
代码如下:
//两两比较,大的往后走
//时间复杂度:O(n^2) 空间复杂度:O(1) 稳定性:稳定
class Solution {
public:void BubbleSort(vector<int>& nums,int n){for(int i=0;i<n-1;i++)//走的趟数{for(int j=0;j<n-i-1;j++)//每走一遍,最大的数字在最后面,走的次数越多,越往后面的数字排序越正确{if(nums[j]>nums[j+1])//两两交换,较大的数字在后面{int temp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}}}vector<int> sortArray(vector<int>& nums) {int n=nums.size();BubbleSort(nums,n);return nums;}
};
4.快速排序

代码如下:
//算法描述:先在数据中找到一个基准,从后往前找比基准小的数字,找到后往前挪动
//从前往后找比基准大的数字,找到往后挪动 重复之前的动作
//一次划分的时间复杂度:O(n) 划分logn次
//时间复杂度:O(nlogn) 空间复杂度:O(logn)(递归的次数)
//快排的缺点:空间复杂度大,不稳定
//快排最大缺点:越有序越慢,完全有序,为O(n^2)退化为选择排序
class Solution {
public:void QuickSort(vector<int>& nums,int left,int right){if(left>=right)//只有一个数或区间不存在{return;}int i=left,j=right;//i在最左边,j在最右边int base=nums[left];//定义最左边的数字为基准while(i<j){while(nums[j]>=base&&i<j)//从后往前找比这个比准数字小的{j--;}while(nums[i]<=base&&i<j)//从前往后找比这个基准数字大的{i++;}swap(nums[i],nums[j]);//找到之后交换两个数字}nums[left]=nums[i];//当i=j时,将基准数字与nums[i]交换nums[i]=base;//在一次完成之后,左边的数字都比基准数字小,右边的数字都比基准数字大QuickSort(nums,left,i-1);//递归左边QuickSort(nums,i+1,right);//递归右边}vector<int> sortArray(vector<int>& nums) {int n=nums.size();QuickSort(nums,0,n-1);return nums;}
};
5.选择排序
代码如下:
//算法描述:每次都从待排序中找到最小值和待排序的第一个交换
//时间复杂度:O(n^2) 空间复杂度:O(1) 稳定性:不稳定
class Solution {
public:void SelectSort(vector<int>& nums,int n){int minIndex;for(int i=0;i<n-1;i++){minIndex=i;for(int j=i+1;j<n;j++){if(nums[minIndex]>nums[j]){minIndex=j;}}swap(nums[i],nums[minIndex]);}}vector<int> sortArray(vector<int>& nums) {int n=nums.size();SelectSort(nums,n);return nums;}
};
相关文章:
排序算法问题
给你一个整数数组 nums,请你将该数组升序排列。 示例 1: 输入:nums [5,2,3,1] 输出:[1,2,3,5] 示例 2: 输入:nums [5,1,1,2,0,0] 输出:[0,0,1,1,2,5] 代码如下: 1.插入排序(简…...
PlotlyJs 指定画布的宽度并页面居中
可以通过CSS样式来实现指定画布的宽度并使其在页面居中。具体方法如下: 在HTML文件中定义一个div,用来包含PlotlyJs画布。如下所示: <div id"plotly-div"></div>在CSS样式中指定该div的宽度和居中方式。如下所示&…...
java基础-----第八篇
系列文章目录 文章目录 系列文章目录一、Java类加载器二、双亲委托模型 一、Java类加载器 JDK自带有三个类加载器:bootstrap ClassLoader、ExtClassLoader、AppClassLoader。 BootStrapClassLoader是ExtClassLoader的父类加载器,默认负责加载%JAVA_HOME…...
【Java 基础篇】StringBuilder的魔力:Java字符串处理探究
在Java编程中,字符串是一个常见的数据类型,用于存储文本信息。然而,与字符串相关的操作可能会导致性能问题,因为字符串是不可变的,每次对字符串进行操作都会创建一个新的字符串对象。为了解决这个问题,Java…...
Shell 编程技巧:批量转换Markdown文件
由于一些原因,需要将以前编写的所有markdown文件转成docx文件,以便做一个备份,特别是原文档中引用的图片需要嵌入docx文件,作本地化保存。先上脚本吧: sudo yum -y install pandoc # set new line char as IFS IFS$\…...
EasyAVFilter的初衷:把ffmpeg.c当做SDK来用,而不是当做EXE来用
之前我们做一个视频点播的功能,大概的流程就是将上传上来的各种格式的视频,用FFmpeg统一进行一次转码,如果probe到视频的编码格式是H.264就调用-vcodec copy,如果probe到视频的编码格式不是H.264就调用-vcodec libx264,…...
内存管理之:内存空间分布和栈攻击(黑客常用攻击手段)
目录 C语言内存管理及栈攻击 内存管理 Linux虚拟内存空间分布(重要) 栈溢出(栈攻击) 堆栈的特点 栈攻击 栈攻击的实现 原理 编译器选项 实现案例 linux修改栈空间大小方式 内存泄漏 如何避免野指针? 如何…...
一米facebook功能点
用户信息批量修改 可批量修改已登录用户的头像、密码、个人说明等信息。 小号批量刷赞、评论 可以批量用facebook小号给帖子、主页等刷赞或评论。 直播帖刷人气/评论/分享 可以直接刷直播帖子的人气、评论,并可一键分享到小组或个人时间线、公共主页等。 小组成员…...
uni-app:监听数据变化(watch监听、@input事件)
方法一:文本框监听,使用input事件 <template><view><input type"text" v-model"wip_entity_name" input"handleInputChange" /></view> </template><script> export default {data() {return {…...
提升C语言的方法?
我个人的习惯,学一门新的编程语言一定是需要目的的。 也就是学这个语言是干什么? 单纯的上学学习C语言一般都是工科的专业作为专业课而开设的学科,这种很多都是使用谭浩强的教材,很多同学也基本没听,所以学习效果也是…...
WPF_布局基础
布局容器 Grid 定义由列和行组成的灵活的网格区域。 行 <Grid.RowDefinitions><RowDefinition/><RowDefinition/></Grid.RowDefinitions> 列 <Grid.ColumnDefinitions><ColumnDefinition/><ColumnDefinition/></Grid.ColumnDe…...
【SA8295P 源码分析】87 - SA8295P HQNX + Android 编译环境搭建指导
【SA8295P 源码分析】87 - SA8295P HQNX + Android 编译环境搭建指导 一、Android 编译环境搭建:Android + sa8295p-hqx-4-2-4-0_hlos_dev_la.tar.gz1.1 更新 Ubuntu 18.04 源路径1.2 安装基础编译环境1.3 设置JDK8 的环境变量1.4 配置sh为bash(默认为dash)1.5 Android 编译…...
java基础-----第九篇
系列文章目录 文章目录 系列文章目录前言一、GC如何判断对象可以被回收前言 一、GC如何判断对象可以被回收 引用计数法:每个对象有一个引用计数属性,新增一个引用时计数加1,引用释放时计数减1,计 数为0时可以回收, 可达性分析法:从 GC Roots 开始向下搜索,搜索所走过的…...
数学建模--整数规划匈牙利算法的Python实现
目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 #整数规划模型--匈牙利算法求解 """ 整数规划模型及概念:规划问题的数学模型一般由三个因素构成 决策变量 目标函数 约束条件;线性规划即以线性函数为目标函数&a…...
OpenCV(十三):图像中绘制直线、圆形、椭圆形、矩形、多边形和文字
目录 1.绘制直线line() 2.绘制圆形circle() 3.绘制椭圆形ellipse() 4.绘制矩形rectangle() 5.绘制多边形 fillPoly() 6.绘制文字putText() 7.例子 1.绘制直线line() CV_EXPORTS_W void line(InputOutputArray img,Point pt1, Point pt2,const Scalar& color,int t…...
[华为云云服务器评测] Unbutnu添加SSH Key、编译启动Springboot项目
系列文章目录 第一章 [linux实战] 华为云耀云服务器L实例 Java、node环境配置 第二章 [linux实战] Unbutnu添加SSH Key、启动Springboot项目 文章目录 系列文章目录前言一、任务拆解二、配置git,添加SSH Key2.1、登录远程主机2.2、配置git用户名和邮箱2.3、生成SSH key2.4、查…...
【MySQL学习笔记】(七)内置函数
内置函数 日期函数示例案例-1案例-2 字符串函数示例 数学函数其他函数 日期函数 示例 获得当前年月日 mysql> select current_date(); ---------------- | current_date() | ---------------- | 2023-09-03 | ---------------- 1 row in set (0.00 sec)获得当前时分秒…...
《Python魔法大冒险》004第一个魔法程序
在图书馆的一个安静的角落,魔法师和小鱼坐在一张巨大的桌子前。桌子上摆放着那台神秘的笔记本电脑。 魔法师: 小鱼,你已经学会了如何安装魔法解释器和代码编辑器。是时候开始编写你的第一个Python魔法程序了! 小鱼:(兴奋地两眼放光)我准备好了! 魔法师: 不用担心,…...
架构,平台,框架的区别和联系
1、解释说明 - 架构:在软件开发中,架构是指软件的整体设计和组织方式。它包括了软件的结构、组件和交互方式等方面的设计。架构定义了系统的高级结构和组织方式,以及各个组件之间的关系和交互方式。一个良好的架构可以提高软件的可维护性、可…...
Mac 安装php多版本,brew安装php8.0
因为需要我要在mac上装两个php版本,先前我已经装过php7.4,下面我们逐步安装php8.0 开始安装8.0: 直接运行安装 brew install php8.0 遇到问题怀疑是仓库太老了,更新一下homebrew ,重新安装 brew update 安装成功了,不过看了下版本好像不能正…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
