【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 支付的顺序)一次购买一杯…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
