【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 支付的顺序)一次购买一杯…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
