【C++】排序算法 --快速排序与归并排序
目录
- 颜色分类(数组分三块思想)
- 快速排序
- 归并排序
颜色分类(数组分三块思想)
给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums ,原地对它们进⾏排序,使得相同颜⾊
的元素相邻,并按照红⾊、⽩⾊、蓝⾊顺序排列。
我们使⽤整数 0、 1 和 2 分别表⽰红⾊、⽩⾊和蓝⾊。
必须在不使⽤库的 sort 函数的情况下解决这个问题。
示例 1:
输⼊:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

class Solution {
public:void sortColors(vector<int>& nums) {int i = 0;int left = i-1;int right = nums.size();//数组分三块while(i<right){if(nums[i] == 1) i++;else if(nums[i] == 0) {swap(nums[i],nums[++left]);i++;}else swap(nums[i],nums[--right]);}}
};
快速排序
类似于前序遍历,先分块,再分治。

class Solution {
public:vector<int> sortArray(vector<int>& nums) {qsort(nums,0,nums.size()-1);return nums;}void qsort(vector<int>& nums,int l,int r){//递归结束条件if(l >= r) return;//要么区间不存在,要么只剩下一个元素int i = l;int left = l-1,right = r+1;int key = nums[i];//数组分块while(i < right){if(nums[i]==key) i++;else if(nums[i]< key) {swap(nums[i],nums[++left]);i++;}else swap(nums[i],nums[--right]);}//分治qsort(nums,l,left);qsort(nums,right,r);}
};
归并排序
类似于后序遍历,先分治,再归并。

class Solution {
public:vector<int> temp;vector<int> sortArray(vector<int>& nums) {temp.resize(nums.size());msort(nums,0,nums.size()-1);return nums;}void msort(vector<int>& nums,int left,int right){//递归结束条件if(left==right) return;//先分治int mid = (left + right) >> 1;msort(nums,left,mid);msort(nums,mid+1,right);//归并int cur1 = left;//遍历左区间int cur2 = mid+1;//遍历右区间int i = 0;//temp数组使用while(cur1 <= mid && cur2 <= right){if(nums[cur1]>nums[cur2]) temp[i++] = nums[cur2++];else temp[i++] = nums[cur1++];}while(cur1 <= mid) temp[i++] = nums[cur1++];while(cur2 <= right) temp[i++] = nums[cur2++];for(int i =left;i <=right ;i++){nums[i] = temp[i-left];//i-left == 0}}
};
相关文章:
【C++】排序算法 --快速排序与归并排序
目录 颜色分类(数组分三块思想)快速排序归并排序 颜色分类(数组分三块思想) 给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums ,原地对它们进⾏排序,使得相同颜⾊ 的元素相邻,并按照红⾊、…...
(Python)根据经纬度从数字高程模型(DEM)文件获取高度
基本介绍 在地理信息系统(GIS)和遥感中,数字高程模型(Digital Elevation Model,简称DEM)是一种表示 地表或地形高程信息的重要数据。DEM数据通常以栅格(raster)形式存在࿰…...
【WPF应用41】WPF中的Expander控件详解
Windows Presentation Foundation(WPF)中的Expander控件是一个用于显示详细信息的交互式UI元素。它允许用户通过点击标题来展开或折叠内容区域。Expander控件通常用于在界面上组织内容,提供一种可见/隐藏的功能,以帮助用户专注于当…...
golang变量初始化顺序
顺序: 1.引用的包 2.全局变量 3.init()函数 4.main()函数 package pkgimport "fmt"func init() {fmt.Println("pkg init") }package mainimport ("fmt"_ "gg/pkg" )var v val()func val() int {fmt.Println("func()…...
魔众 文库配置异步转换
同步转换 系统默认使用同步转换,即用户上传文档提交接口瞬间,系统会立即进行转换。 同步转换容易造成页面卡顿,转换时间超长的情况下,系统接口会超时。 异步转换 系统支持异步转换,即用户上传文档提交接口瞬间&…...
创建型模式--2.简单工厂模式【人造恶魔果实工厂1】
1. 工厂模式的特点 在海贼王中,作为原王下七武海之一的多弗朗明哥,可以说是新世界最大的流氓头子,拥有无上的权利和无尽的财富。他既是德雷斯罗萨国王又是地下世界的中介,控制着世界各地的诸多产业,人造恶魔果实工厂就…...
一些考研经验
前言 考研结束已有半个月,之前一直想写经验贴,奈何感觉自己本身就比较菜,考了两年才堪堪上岸,所以有些犹豫,拖拖沓沓到现在,思虑再三最终决定把自己对于考研的一些拙见记录一下,供各位参考。 …...
StockTrading AI小模型股票自动交易系统 转载
Stock-Trading StockTrading AI小模型股票自动交易系统 项目文档 Stock-Trading 语雀 项目展示 功能介绍 对接证券平台,实现股票自动化交易使用QuartZ定时任务调度,每日自动更新数据使用DL4J框架实现LSTM模型指导股票买入,采用T1短线交易策…...
01背包问题合集 蓝桥OJ
一、蓝桥OJ 1174小明的背包1 模板题 思路: 用二维数组dp判断最大价值,i表示物品数量,j表示物品体积,如果 j > V 则无需继续, j > w 物品还能再增加,同样价值也增加,否则继承之前的价值&am…...
Nuxt3 实战 (三):使用 release-it 自动管理版本号和生成 CHANGELOG
release-it 能做什么? 增加版本号并提交 Git生成变更日志(Changelog)并提交到 Git创建 Git 标签并推送到远程仓库发布到 npm 等软件仓库在 GitHub、GitLab 等平台创建发行版 前置知识 在看这篇文章之前,我们有必要了解一下 Sem…...
鸿蒙OS开发实战:【自动化测试框架】使用指南
概述 为支撑HarmonyOS操作系统的自动化测试活动开展,我们提供了支持JS/TS语言的单元及UI测试框架,支持开发者针对应用接口进行单元测试,并且可基于UI操作进行UI自动化脚本的编写。 本指南重点介绍自动化测试框架的主要功能,同时…...
算法(二分查找)
1.给你一个非负整数 x ,计算并返回 x 的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1…...
运筹学基础(六)列生成算法(Column generation)
文章目录 前言从Cutting stock problem说起常规建模Column generation reformulation 列生成法核心思想相关概念Master Problem (MP)Linear Master Problem (LMP)Restricted Linear Master Problem (RLMP)subproblem(核能预警,非常重要) 算法…...
[阅读笔记] 电除尘器类细分市场2023年报
0.原始链接: 2023年除尘行业评述及2024年发展展望-北极星大气网 中国环保产业协会 供稿 1.重要信息摘录 市场占有率最大的是电除尘和袋式除尘行业装备产品名录: 国家鼓励发展的重大环保技术装备目录(2023年版)权威评审机构:…...
Kubernetes学习笔记11
k8s集群核心概念:pod: 在K8s集群中是不能直接运行容器的,K8s的最小调度单元是Pod,我们要使用Pod来运行应用程序。 学习目标: 了解pod概念: 了解查看pod方法 了解创建pod方法 了解pod访问方法 了解删除…...
✌2024/4/3—力扣—无重复字符的最长子串
代码实现: 解法一:暴力法 int lengthOfLongestSubstring(char *s) {int hash[256] {0};int num 0;for (int i 0; i < strlen(s); i) {int count 0;for (int j i; j < strlen(s); j) {if (hash[s[j]] 0) {hash[s[j]];count;num num > cou…...
Tauri 进阶使用与实践指南
Tauri 进阶使用与实践指南 调试技术 在 Tauri 应用开发中,调试分为两大部分:Web 端与 Rust 控制台。 Web 端调试 在 Web 端界面,可以直接采用浏览器内置的开发者工具进行调试。在 Windows 上,可以通过快捷键 Ctrl Shift i 打…...
2024年最新社交相亲系统源码下载
最新相亲系统源码功能介绍 参考:相亲系统源码及功能详细介绍 相亲系统主要功能 (已完成) 相亲系统登录注册 相亲系统会员列表 相亲系统会员搜索 相亲系统会员详情 相亲系统会员身份认证 - 对接阿里云 相亲系统资源存储 - 对接七…...
git知识
如何将develop分支合并到master分支 #简单版 git checkout master git pull origin master git merge origin/develop # 解决可能的冲突并提交 git push origin master#复杂版 git checkout master # 拉取远程 master 分支的最新代码并合并到本地 git pull origin master # 拉…...
代码随想录算法训练营第三十五天|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球
代码随想录算法训练营第三十五天|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球 860.柠檬水找零 在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
