当前位置: 首页 > news >正文

常见排序算法(C++)

评判一个排序算法时除了时间复杂度和空间复杂度之外还要考虑对cache的捕获效果如何,cache友好的排序算法应该对数据的访问相对集中,快速排序相较于堆排序优点就是在于对cache的捕获效果好。

堆排序
时间复杂度:O(n log n )
空间复杂度 O(1) 不稳定
cache不友好

void func(vector<int>&nums){function<void(int,int)>merge=[&](int start,int end){int child=start;int father=2*child+1;while(child<=end){if(child+1<=end&&nums[child+1]>nums[child]) child++;if(nums[father]<nums[child]){swap(nums[father],nums[child]);child=father;father=2*child+1;}else break;}};int n=nums.size();for(int i=n/2-1;i>=0;i--){merge(i,n-1);}for(int i=n-1;i>=0;i--){swap(nums[0],nums[i]);merge(0,i-1);}
}

快速排序
时间复杂度O(n log n)- O(n^2)
空间复杂度 O(1)
cache友好

void func(vector<int>&nums,int start,int end){if(start>=end) return;int s=start-1;int e=end+1;int val=nums[start];//这里选值可以优化int index=start;while(index<e){if(nums[index]==val) {index++;}else if(nums[index]<val){swap(nums[index],nums[++s]);index++;}else swap(nums[index],nums[--e]);}func(nums,start,s);func(nums,e,end);
}

归并排序
时间复杂度 O(n log n)
空间复杂度 O(n)
cache友好

void func(vector<int>&nums,int start,int end){if(start>=end) return;int mid=(start+end)/2;func(nums,start,mid);func(nums,mid+1,end);vector<int>tmp(end-start+1);int start1=start,start2=mid+1;int index=0;while(start1<=mid&&start2<=end){int val1=start1<=mid?nums[start1]:INT_MAX;int val2=start2<=end?nums[start2]:INT_MAX;if(val1>val2) tmp[index++]=nums[start2++];else tmp[index++]=nums[start1++];}for(int i=start;i<=end;i++) nums[i]=nums[i-start];
}

选择排序
时间复杂度 O(n^2)
空间复杂度 O(1)
cache不友好

void func(vector<int>&nums){int n=nums.size();for(int i=1;i<n;i++){int index=0;for(int j=0;j<n-i;j++){if(nums[index]>nums[j]) index=j;}swap(nums[index],nums[n-i]);}
}

插入排序
时间复杂度 O(n^2)
空间复杂度 O(1)
cache友好

void func(vector<int>&nums){int n=nums.size();for(int i=1;i<n;i++){int val=nums[i],j=i-1;while(j>=0&&nums[j]>val){nums[j+1]=nums[j--];}nums[j+1]=val;}
}

冒泡排序
时间复杂度 O(n^2)
空间复杂度 O(1)
cache不友好

void func(vector<int>&nums){int n=nums.size();for(int i=0;i<n;i++){bool b=true;for(int j=i+1;j<n;j++){if(nums[i]>nums[j]) {b=false;swap(nums[i],nums[j]);}}if(b) break;}
}

相关文章:

常见排序算法(C++)

评判一个排序算法时除了时间复杂度和空间复杂度之外还要考虑对cache的捕获效果如何&#xff0c;cache友好的排序算法应该对数据的访问相对集中&#xff0c;快速排序相较于堆排序优点就是在于对cache的捕获效果好。 堆排序 时间复杂度&#xff1a;O&#xff08;n log n &#xf…...

多线程编程互斥锁mutex的创建

在Linux下的多线程编程中&#xff0c;互斥锁&#xff08;mutex&#xff09;的创建主要有两种方式&#xff1a;静态分配和动态分配。这两种方式的主要区别在于互斥锁的生命周期和初始化方式。 静态分配&#xff08;静态方式&#xff09; 静态分配方式是在程序编译时就已经确定互…...

在 SpringBoot3 中使用 Mybatis-Plus 报错

在 SpringBoot3 中使用 Mybatis-Plus 报错 Property ‘sqlSessionFactory’ or ‘sqlSessionTemplate’ are required Caused by: java.lang.IllegalArgumentException: Property sqlSessionFactory or sqlSessionTemplate are requiredat org.springframework.util.Assert.no…...

【libwebrtc】基于m114的构建

libwebrtc A C++ wrapper for binary release, mainly used for flutter-webrtc desktop (windows, linux, embedded).是 基于m114版本的webrtc 最新(20240309 ) 的是m122了。官方给出的构建过程 .gclient 文件 solutions = [{"name" : src,"url...

ansible-playbook的角色(role)

1前言 角色目录如下&#xff08;分别为httpd角色和nginx角色&#xff09; handlers/ &#xff1a;至少应该包含一个名为 main.yml 的文件&#xff1b; 其它的文件需要在此文件中通过include 进行包含 vars/ &#xff1a;定义变量&#xff0c;至少应该包含一个名为 main.yml 的…...

SNR = 6.02N + 1.76dB 公式推导

简介 接触ADC或DAC时您一定会碰到这个经常被引用的公式&#xff0c;用于计算转换器理论信噪比 (SNR)。与其盲目地相信表象&#xff0c;不如从根本上了解其来源&#xff0c;因为该公式蕴含着一些微妙之 处&#xff0c;如果不深入探究&#xff0c;可能导致对数据手册技术规格和转…...

归并排序 刷题笔记

归并排序的写法 归并排序 分治双指针 1.定义一个mid if(l>r)return ; 2.分治 sort(q,l,mid); sort(q,mid1,r); 3. 双指针 int il,jmid,k0; 将双序列扫入 缓存数组 条件 while(i<mid&&j<r) 两个数列比较大小 小的一方 进入缓存数组 4. 扫尾 while(…...

字节一面:TCP 和 UDP 可以使用同一个端口吗?

数据包是计算机网络通信的核心&#xff0c;包含头部和数据负载。TCP和UDP协议在传输层使用端口号区分服务和应用。操作系统通过IP头部中的协议字段和端口号来管理网络流量&#xff0c;确保TCP和UDP流量即使共用端口号也不会相互干扰。 在现代计算机网络中&#xff0c;数据传输…...

java guide 八股

Java语言特点 简单易学、面向对象&#xff08;继承、封装、多态&#xff09;、平台无关性&#xff08;Java虚拟机jvm&#xff09;、支持多线程、可靠、安全、高效、支持网络编程、编译与解释共存 JVM&#xff1a;Java虚拟机&#xff08;跨平台的关键&#xff09; JRE&#xff…...

Windows上使用client-go远程访问安装在本地WMware上的Linux虚拟机里的minikube

我在自己的Windows上安装了WMware&#xff0c;并在WMware上安装了CentOS操作系统&#xff0c;然后在CentOS上创建了一个叫minikube的用户&#xff0c;使用minikube用户启动了一个minikube集群&#xff0c;但是我在Windows上使用client-go并无法连通minikube&#xff0c;搜遍全网…...

Linux/Ubuntu/Debian基本命令:命令行历史记录

一组与类 Unix 环境中的命令行(Terminal)历史记录和命令调用相关的键盘快捷键&#xff1a; Ctrl R&#xff1a; 启动对以前使用过的命令的反向搜索。 当你键入时&#xff0c;它将查找并显示与输入的字符匹配的最新命令。Ctrl G: 退出历史搜索模式&#xff0c;不运行命令。 如…...

倒计时32天

L1-032 Left-pad - 2024团体程序设计天梯赛&#xff08;历年真题&#xff09;练习集 (pintia.cn) #include<bits/stdc.h> using namespace std; #define int long long const int N2e56; const int inf0x3f3f3f3f; void solve() {int n;char s;cin>>n>>s;ge…...

模型驱动架构MDA

MDE 模型驱动工程&#xff08;MDE, Model-Driven Engineering&#xff09;是软件工程的一个分支&#xff0c;它将模型与建模拓展到软件开发的所有方面&#xff0c;形成一个多维建模空间&#xff0c;从而将工程活动建立在这些模型的映射和转换之上。[1] MDE的基本原则是将模型视…...

std::error::Error 和 std::io::Error 的区别和用法

std::error::Error 和 std::io::Error 在 Rust 中都是用于错误处理的类型&#xff0c;但它们各自有不同的用途和场景。 std::error::Error&#xff1a; std::error::Error 是一个 trait&#xff0c;它定义了错误处理的基本接口。这个 trait 通常由其他具体的错误类型实现&…...

16 OpenCV Laplance算子

文章目录 图像的二阶导数Laplance算子代码示例 图像的二阶导数 在二阶导数的时候&#xff0c;最大变化处的值为零即边缘是零值。通过二阶 导数计算&#xff0c;依据此理论我们可以计算图像二阶导数&#xff0c;提取边缘。 Laplance算子 void Laplacian( InputArray src, Output…...

hardhat学习笔记

hardhat学习笔记会不定时填充内容。 初始化项目 yarn init 安装hardhat依赖 yarn add --dev hardhat 初始化 Hardhat yarn hardhat 代码格式化 yarn add --dev prettier prettier-plugin-solidity 项目中增加.prettierrc 与 .prettierignore 配置文件统一格式&#xff0…...

算法刷题day28

目录 引言一、截断数组二、双端队列三、日期统计 引言 这几道题是周赛里的几道题目&#xff0c;第一道题目我没用这种方法&#xff0c;但还是做出来了&#xff0c;用的一种比较特殊的思考方法&#xff0c;就是把每一个点都判断出来&#xff0c;不满足要求的就舍弃&#xff0c;…...

vivado 使用Design Runs窗口、

使用Design Runs窗口 “设计运行”窗口显示在项目中创建的所有合成和实现运行。它包括用于配置、管理和启动运行的命令。 打开Design Run窗口 选择窗口 →  Design Runs打开“Design Runs”窗口。 设计运行窗口功能 •每个实现运行都缩进显示在其子级的合成运行下面。 …...

基于YOLOv8的手机摄像头的自动检测系统

文章大纲 数据集网络爬虫开源数据集标注目标定义标注标准标注工具标签更换脚本自制数据集下载地址自动检测系统设计与搭建模型训练与准确率代码仓库下载地址参考文献与学习路径随着移动通信技术的飞速发展,消费者对移动终端的要求也越来越高,各厂商纷纷提出自己的特色卖点,其…...

Ubuntu18.04添加内核模块(字符设备)

Ubuntu18.04添加内核模块&#xff08;字符设备&#xff09; 虚拟机Ubuntu18.04&#xff08;内核版本linux-5.4.0-135-generic&#xff09; 参考 嵌入式Linux驱动开发&#xff08;一&#xff09;——字符设备驱动框架入门 1 编译内核模块 创建字符设备代码文件char_dev.c&a…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...