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]; …...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
