C++基础算法④——排序算法(快速、归并附完整代码)
快速排序
快速排序是对冒泡排序的一种改进。
它的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,以达到整个序列有序。
假设我们现在对 6 1 2 7 9 3 4 5 1 0 8 这个10个数进行排序。
int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];qsort(1,n);for(int i=1;i <=n;i++){cout<<a[i]<<" ";} return 0;
}
首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列:
int a[10001];
void qsort(int l,int r){int i,j,mid;i=l+1,j=r;mid=a[l];

可以发现,i从第二个位置开始,j从最后一个位置开始;当 i 指向的值 大于基准值6 而且 当 j 指向的值 小于基准值6,就把这两个值交换,然后接着往下继续比。

while(i<=j){ //当 i j 没有碰到while(a[i]<mid) i++;while(a[j]>mid) j--;if(i<=j){swap(a[i],a[j]);i++; j--;}}

当 i j 相遇了,就把 j指向的值 与基准数交换。
swap(a[j],a[l]); //交换基准数

可以发现,一趟完毕,原基准数6的左边值一定比6小,右边比6大。这样就确定了基准数6的排序。
接下来,对于6左边的序列3 1 2 5 4和右边的序列9 7 10 8分别进行快速排序。
把整体分了左右边,再把左边的序列3 1 2 5 4看成新的重新进行快速排序。不断地分解。

所以这个排序运用了分治的思想!
完整代码:
#include<bits/stdc++.h>
using namespace std;
int a[10001];
void qsort(int l,int r){int i,j,mid;i=l+1,j=r;mid=a[l];while(i<=j){while(a[i]<mid) i++;while(a[j]>mid) j--;if(i<=j){swap(a[i],a[j]);i++; j--;}}swap(a[j],a[l]); //交换基准数if(l<j) qsort(l,j-1);if(i<r) qsort(i,r);
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];qsort(1,n);for(int i=1;i <=n;i++){cout<<a[i]<<" ";} return 0;
}
快速排序是不稳定的排序方法,时间复杂度是O(nlog2n),速度快,平均时间来说,快速排序是最好的一种内部排序方法。但快速排序需要一个栈空间实现递归,每一趟排序都会将记录序列分割成两个子序列,栈最大深度为log(n+1)。
归并排序
归并的思路(分治)是把一个大问题a拆解成两个小问题b和c,解决了两个子问题再整合一下,就解决了原问题。用递归的方法,先分解再合并(分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突)。
- 稳定性:稳定;
- 空间复杂度O(n);
- 复杂度:时间复杂度O(nlogn);
- 优缺点:效率高且稳定,但是消耗的辅助空间与原数据空间成正比。
int main(){cin>>n;for(int i=1;i<=n;i++){ //输入 cin>>a[i];}//归并排序mergesort(1,n);for(int i=1;i<=n;i++){ //输出 cout<<a[i]<<" ";}return 0;
}
- 递归分解

不断地二分分解,拆左右。
void mergesort(int l,int r){int mid = (l+r)/2;if(l==r) return ;mergesort(l,mid); //左边排序mergesort(mid+1,r);//右边排序//上面已经拆成一个一个 merge(l,mid,mid+1,r); //合并操作
}
分解到1个值,然后再合并排序。合并的思路看成:左边是有序的a数组;右边是有序的b数组。两数组开始比较,小的值依次存到c数组。
int a[100],c[100],n,cnt;
void merge(int left,int i,int j,int right){int lenc = left;int len1 = left; //左边开头 看成a[] int len2 = j; //右边开头 看成b[] while(len1<=i && len2<=right){ //并c[] if(a[len1]<a[len2]){ //左边小于右边 c[lenc++] = a[len1++];}else{//右边小于左边c[lenc++] = a[len2++];}} while(len1<=i){c[lenc++] = a[len1++];} while(len2<=right){c[lenc++] = a[len2++];}//把排好序的c数组存回a数组里面for(int k=left;k<=right;k++){a[k]=c[k];}
}
完整代码:
#include<bits/stdc++.h>
using namespace std;
int a[100],c[100],n,cnt;
void merge(int left,int i,int j,int right){int lenc = left;int len1 = left; //左边开头 看成a[] int len2 = j; //右边开头 看成b[] while(len1<=i && len2<=right){ //并c[] if(a[len1]<a[len2]){ //左边小于右边 c[lenc++] = a[len1++];}else{//右边小于左边c[lenc++] = a[len2++];}} while(len1<=i){c[lenc++] = a[len1++];} while(len2<=right){c[lenc++] = a[len2++];}//把排好序的c数组存回a数组里面for(int k=left;k<=right;k++){a[k]=c[k];}
} void mergesort(int l,int r){int mid = (l+r)/2;if(l==r) return ;mergesort(l,mid); //左边排序mergesort(mid+1,r);//右边排序//上面已经拆成一个一个 merge(l,mid,mid+1,r); //合并操作
}
int main(){cin>>n;for(int i=1;i<=n;i++){ //输入 cin>>a[i];}//归并排序mergesort(1,n);for(int i=1;i<=n;i++){ //输出 cout<<a[i]<<" ";}return 0;
}相关文章:
C++基础算法④——排序算法(快速、归并附完整代码)
快速排序 快速排序是对冒泡排序的一种改进。 它的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行快速排序,以达到整个序列有序。 假设我们现在对 …...
高防CDN如何在防护cc上大显神通
高级防御CDN(Content Delivery Network)在对抗CC(HTTP Flood)攻击方面扮演着关键的角色,具备以下重要职能和作用: 流量分散:CC攻击的目标是通过大规模的HTTP请求使服务器过载,从而导…...
解决CSS中height:100%失效的问题
出现BUG的场景,点击退出到登录页面,发现高度不对 上面出现了一种只是占了内容的高度,没有占满100%,为什么会出现这种情况呐? 让div的height"100%",执行网页时,css先执行到࿰…...
小红书穿搭类种草营销怎么做?纯干货
在众多营销方式中,穿搭类种草营销以其独特的优势在小红书平台上崭露头角。穿搭类种草营销,以其独特的优势,成为了品牌和商家推广产品的重要方式。其优势主要体现在以下几个方面: 1. 高度相关性:小红书平台的用户主要是…...
什么是ARFF文件,以.arff结尾
关于arff,主要涉及三个输入类:概念、实例和属性。 1.概念简单而言就是需要被处理的东西, 2. 实例这个词有些陌生,但是可以大致认为其为样本, 3. 属性就是数据表中的一列。 为什么要用arff?(arff介绍&#x…...
华为OD机考算法题:计算疫情扩散时间
题目部分 题目计算疫情扩散时间难度难题目说明在一个地图中(地图由 n * n 个区域组成)有部分区域被感染病菌感染区域每天都会把周围(上下左右)的4个区域感染。 请根据给定的地图计算多少天以后,全部区域都会被感染。 如果初始地图上所有区域全部都被感染࿰…...
29岁从事功能测试5年被辞,面试4个月还没到工作......
最近一个32岁的老同学因为被公司辞退,聊天过程中找我倾诉,所以写下了这篇文章。 他是15年二本毕业,学的园林专业,人属于比较懒的那种,不爱学习,专业学的也一般。实习期间通过校招找到了一份对口的工作。但…...
再记【fatal error C1001: 内部编译器错误】的一个原因
平台:Windows 11、Visual Studio 2022 报错信息 已启动生成... 1>------ 已启动生成: 项目: PointMatchingModel, 配置: Debug x64 ------ 1>PointMatchingModel.cpp 1>C:\tools\vcpkg\installed\x64-windows\include\pcl\registration\impl\ia_fpcs.hpp…...
数据分析、大数据分析和人工智能之间的区别
数据分析、大数据分析和人工智能近年来十分热门,三者之间看起来有相似之处,也有不同之处。今天就来谈谈三者间的区别。 数据分析 数据分析是指对数据进行分析,从中提取有价值的信息,以支持企业或组织的决策制定。数据分析可以针对…...
Spring系列之基础
目录 Spring概述 Spring的优点 Spring Framework的组成 总结 Spring概述 Spring 是目前主流的 Java Web 开发框架,是 Java 世界最为成功的框架。该框架是一个轻量级的开源框架,具有很高的凝聚力和吸引力。它以Ioc(控制反转)和…...
Android开发知识学习——TCP / IP 协议族
文章目录 学习资源来自:扔物线TCP / IP 协议族TCP连接TCP 连接的建立与关闭TCP 连接的建立为什么要三次握手? TCP 连接的关闭为什么要四次挥手? 为什么要⻓连接? 常见面试题课后题 学习资源来自:扔物线 TCP / IP 协议…...
思维训练 第四课 省略句
系列文章目录 文章目录 系列文章目录前言一、省略的十五种情况1.并列复合句中某些相同成分的省略2.在用when, while, if, as if, though, although, as ,until, whether等连词引导的状语从句中,如果谓语有be,而主语又跟主句的主语相同或是(从句主语是&am…...
soul协议算法
逆向工程技术是指对软件或应用程序进行逆向分析以了解其内部机制和功能的过程。虽然我无法详细介绍"Soul App"的逆向工程技术,但以下是一些常见的逆向工程技术,可能与你的研究相关: 1. 反汇编(Disassembly)…...
电子产品的认证体系
一、国内认证体系 1、CNAS认可:对认证机构的认可 CNAS全称是China National Accreditation Service for Conformity Assessment,中国合格评定国家认可委员会,由国家认证认可监督管理委员会(CNCA)批准设立并授权的唯一…...
大厂面试题-网络四元组
四元组,简单理解就是在TCP协议中,去确定一个客户端连接的组成要素,它包括源 IP地址、目标IP地址、源端口号、目标端口号。 正常情况下,我们对于网络通信的认识可能是这样(如图)。 服务端通过Server Socket建立一个对指定端口号…...
【通义千问“助力用户运营,无代码开发实现API连接广告推广和CRM】
通义千问:阿里云推出的超大规模语言模型 通义千问,是阿里云推出的一个超大规模的语言模型,功能包括多轮对话、文案创作、逻辑推理、多模态理解、多语言支持。这款产品的主要目标是帮助用户在无需编程的情况下,通过API连接广告推广…...
数据结构第一课-----------数据结构的介绍
作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 🎂 作者介绍: 🎂🎂 🎂 🎉🎉🎉…...
Python武器库开发-常用模块之OS模块(十一)
常用模块之OS模块(十一) Python中的 os 模块提供了非常丰富的方法用来处理文件和目录,可以执行一些操作系统的功能。常用的方法如下表所示: 序号方法描述1os.access(path, mode)检验权限模式2os.chdir(path)改变当前工作目录3os.chflags(path, flags)设…...
Vectrosity 插件使用
1 下载 https://download.csdn.net/download/moonlightpeng/88490704?spm1001.2014.3001.5503 2 使用,目前在2020.3.3上测试可以 导入时选5.6 再导入demo...
数据结构详细笔记——并查集
文章目录 逻辑结构存储结构并、查代码实现Union 操作的优化Find 操作的优化(压缩路径) 逻辑结构 集合:将各个元素划分为若干个互不相交的子集的集合 森林是m(m>0)棵互不相交的树的集合 存储结构 #define SIZE 13 int UFSets[SIZE]; …...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
前端开发者常用网站
Can I use网站:一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use:Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站:MDN JavaScript权威网站:JavaScript | MDN...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...
