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

Acwing 排序

1.快速排序

主要思想:基于分治思想。通过选择一个基准元素,将数组分为两部分,左边部分元素都小于等于基准,右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。

分区逻辑:双指针算法

  • 左指针i从左往右找到第一个大于等于基准的元素
  • 右指针从右往左找到第一个小于等于基准的元素
  • 交换两个元素,使得左侧部分小于等于基准,右侧部分大于等于基准

l是待排序区间的左边界,r是右边界

  1. 确定分界点x(基准),可以取左边界的值q[l],或右边界的值q[r],或者中间位置的值q[(l + r)/2]
  2. 根据基准值,调整区间,使得左半边区间的值全都≤ x,右半边区间的值全都≥ x .
    采用双指针:左指针i从左边界l-1开始,往右扫描,右指针j从右边界r+1开始,往左扫描

为什么初始是l-1,r+1?
因为后续的不管执行交换与否,首先都先将i,j向内移动一位,所以一开始的两个指针都设置为超出边界一个位置

当满足条件q[i] < x时,i右移;直到不满足条件时,即q[i] >= xi停下;

然后移动右指针jj 当满足条件q[j] > x时,j左移;直到不满足条件时,即q[j] <= xj停下;

交换q[i]q[j]i右移一位,j左移一位,重复上面的操作,直到ij相遇(最终i和j的位置为:i==j或i=j+1)。 此时左半区间的数都满足≤x,且左半区间的最后一个数的下标为j,右半区间的数都满足≥ x,且右半区间的第一个数的下标为i

  1. 递归处理左右两段
    • 若用j来作为区间的分界,则[l, j] 都是≤x[j + 1, r]都是≥x
    • 若用i来作为区间的分界,则[l, i - 1]都是≤x[i, r]都是≥x

注意:
递归取[l, j][j + 1, r]区间时,基准值不能取右边界x=q[r],不然会出现死循环问题,此时常取左边界x=q[l]或中间值 (eg:1,2 会出现死循环)
同理当递归取[l, i - 1][i,r]区间时,基准值不能取左边界x=q[l],不然会出现死循环问题,此时常取左边界x=q[r] 或中间值 (eg:1,2 会出现死循环)
快排不稳定,平均时间复杂度nlogn。最坏情况(例如数组已经有序的情况下),时间复杂度为 𝑂 ( 𝑛 2 ) 𝑂(𝑛^2) O(n2),但通过选择中间值作为基准,可以减少最坏情况的发生。

这里给出一个快排的板子:

// 快速排序函数,q[] 是待排序的数组,l 是左边界,r 是右边界
void quick_sort(int q[], int l, int r) {if (l >= r) return;  // 递归终止条件:当左边界大于或等于右边界时停止递归// 选择中间元素作为基准数,并初始化左右指针 i 和 jint x = q[(l + r) / 2], i = l - 1, j = r + 1;// 使用双指针法进行分区while (i < j) {// 从左边开始找到第一个大于等于基准数的元素do i++; while (q[i] < x);// 从右边开始找到第一个小于等于基准数的元素do j--; while (q[j] > x);// 如果 i 和 j 没有相遇,交换 q[i] 和 q[j],确保左边都比基准数小,右边都比基准数大if (i < j) swap(q[i], q[j]);}// 递归处理左半部分quick_sort(q, l, j);// 递归处理右半部分quick_sort(q, j + 1, r);
}

Acwing 785.快速排序
在这里插入图片描述
具体实现代码(详解版):

#include <iostream>
#include <algorithm>using namespace std;const int N = 1e6 + 10;  int n;        
int q[N];     // 存储待排序的数组// 快速排序函数,q[] 是待排序的数组,l 是左边界,r 是右边界
void quick_sort(int q[], int l, int r) {if (l >= r) return;  // 递归终止条件:当左边界大于或等于右边界时停止递归// 选择中间元素作为基准数,并初始化左右指针 i 和 jint x = q[(l + r) / 2], i = l - 1, j = r + 1;// 使用双指针法进行分区while (i < j) {// 从左边开始找到第一个大于等于基准数的元素do i++; while (q[i] < x);// 从右边开始找到第一个小于等于基准数的元素do j--; while (q[j] > x);// 如果 i 和 j 没有相遇,交换 q[i] 和 q[j],确保左边都比基准数小,右边都比基准数大if (i < j) swap(q[i], q[j]);}// 递归处理左半部分quick_sort(q, l, j);// 递归处理右半部分quick_sort(q, j + 1, r);
}int main() {cin >> n;  for (int i = 0; i < n; i++) cin >> q[i];quick_sort(q, 0, n - 1);for (int i = 0; i < n; i++) cout << q[i] << ' ';cout << endl;  return 0;  
}

Acwing 786.第k个数
在这里插入图片描述
实现思路:直接进行快排,然后注意第k个数的数组下标是k-1,即答案就是q[ k - 1].

#include <iostream>
#include <algorithm>using namespace std;const int N = 1e6 + 10;
int n , k;
int q[N];//快速排序
void quick_sort(int q[],int l , int r){if(l >= r) return ;int x = q[(l + r) / 2], i = l - 1, j = r + 1;while(i < j){do i ++ ; while(q[i] < x);do j -- ; while(q[j] > x);if(i < j) swap(q[i] , q[j]);}quick_sort(q, l ,j);quick_sort(q, j + 1 ,r);
}int main(){cin >> n >> k ;for(int i = 0 ; i < n ; i ++) cin >> q[i];quick_sort(q, 0 , n - 1);//第k个数cout << q[k - 1] << endl;return 0;
}

2.归并排序

主要思想:也是基于分治思想

  • 先确认分界点(下标):一般取中间点(l + r) /2;
  • 对左右两个子数组分别进行递归排序
  • 将两个排好序的子数组合二为一

实现思路:设置左右指针和一个临时数组temp,左指针指向左区间的的第一个元素,右指针指向右区间的第一个元素,循环比较左右指针所指元素,两者较小的元素放入temp数组中,指针后移继续比较。直至某一指针到达末尾,将其中一个未放置完的区间的数再都放入temp数组。

归并排序的时间复杂度为 𝑂 ( 𝑛 l o g 𝑛 ) 𝑂(𝑛log𝑛) O(nlogn),即使在最坏的情况下也是如此。它的性能较为稳定,适用于大规模数据的排序任务

归并排序的板子:

const int N = 1e6 + 10;  // 定义数组容量为 10^6 + 10int n;
int q[N], temp[N];  // q[] 存储待排序的数组,temp[] 是归并时的临时数组// 归并排序函数,q[] 是待排序的数组,l 是左边界,r 是右边界
void merge_sort(int q[], int l, int r) {if (l >= r) return;  // 递归终止条件:如果只有一个元素,直接返回int mid = (l + r) / 2;  // 取中间点,将数组分成两部分// 递归处理左半部分merge_sort(q, l, mid);// 递归处理右半部分merge_sort(q, mid + 1, r);// 合并两个有序的部分int i = l, j = mid + 1, k = 0;  // i 追踪左半部分,j 追踪右半部分,k 追踪临时数组while (i <= mid && j <= r) {if (q[i] <= q[j]) temp[k++] = q[i++];  // 左边小或相等时,将左边的元素放入临时数组else temp[k++] = q[j++];               // 否则将右边的元素放入临时数组}// 如果左半部分还有剩余元素,放入临时数组while (i <= mid) temp[k++] = q[i++];// 如果右半部分还有剩余元素,放入临时数组while (j <= r) temp[k++] = q[j++];// 将临时数组中的元素拷贝回原数组的对应位置for (i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
}

Acwing 787.归并排序
在这里插入图片描述
具体实现代码(详解版):

#include <iostream>
using namespace std;const int N = 1e6 + 10;  // 定义数组容量为 10^6 + 10int n;
int q[N], temp[N];  // q[] 存储待排序的数组,temp[] 是归并时的临时数组// 归并排序函数,q[] 是待排序的数组,l 是左边界,r 是右边界
void merge_sort(int q[], int l, int r) {if (l >= r) return;  // 递归终止条件:如果只有一个元素,直接返回int mid = (l + r) / 2;  // 取中间点,将数组分成两部分// 递归处理左半部分merge_sort(q, l, mid);// 递归处理右半部分merge_sort(q, mid + 1, r);// 合并两个有序的部分int i = l, j = mid + 1, k = 0;  // i 追踪左半部分,j 追踪右半部分,k 追踪临时数组while (i <= mid && j <= r) {if (q[i] <= q[j]) temp[k++] = q[i++];  // 左边小或相等时,将左边的元素放入临时数组else temp[k++] = q[j++];               // 否则将右边的元素放入临时数组}// 如果左半部分还有剩余元素,放入临时数组while (i <= mid) temp[k++] = q[i++];// 如果右半部分还有剩余元素,放入临时数组while (j <= r) temp[k++] = q[j++];// 将临时数组中的元素拷贝回原数组的对应位置for (i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
}int main() {cin >> n;  // 输入数组长度// 读取 n 个元素存入数组 q 中for (int i = 0; i < n; i++) cin >> q[i];// 调用归并排序算法,排序整个数组merge_sort(q, 0, n - 1);// 输出排序后的数组for (int i = 0; i < n; i++) cout << q[i] << ' ';cout << endl;  // 换行return 0;  // 程序结束
}

Acwing.788求逆序对的数量
在这里插入图片描述
实现思路:

  • 根据归并排序的思想,将数组分为各自有序的左右两个区间[l,mid],[mid+1,r],采用双指针开始分别指向两个区间的第一个元素,相互比较选出较小的那个元素,然后后移,不断循环,直到一个区间遍历完。
  • 在比较过程中,设i指向左区间,j指向右区间,由于两个区间各自有序,逆序对只会出现一种情况,即左区间存在大于右区间元素的元素。
  • a[i]>a[j],则左区间中从i开始到mid的元素都大于a[j],与a[j]组成逆序对,数量为mid-i+1

注意:对于给定n个数,最坏的情况为逆序,则逆序对数为n(n-1)/2个,题中数据个数范围为100000,则最大结果会超出int的存储范围(-231~231-1),所以虽好使用long long来存储最终结果

具体实现代码(详解版):

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;  
const int N = 1e6 + 10;  
int n;  
int q[N], temp[N];  // q[] 用于存储输入数组,temp[] 用于合并时的临时数组// 归并排序函数,返回区间 [l, r] 的逆序对数量
LL merge_sort(int l, int r) {if (l >= r) return 0;  // 如果区间内只有一个元素,返回 0,表示没有逆序对int mid = (l + r) / 2;  // 找到中间位置// 递归处理左半部分和右半部分,并计算各自的逆序对数量LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);// 合并两个有序区间,同时统计逆序对int i = l, j = mid + 1, k = 0;  // i 指向左区间,j 指向右区间,k 是 temp 的索引while (i <= mid && j <= r) {if (q[i] <= q[j]) {temp[k++] = q[i++];  // 如果左区间的元素小于等于右区间,取左区间的元素} else {temp[k++] = q[j++];  // 否则取右区间的元素res += mid - i + 1;  // 统计逆序对的数量,mid - i + 1 表示当前左区间剩余的元素个数}}// 如果左区间还有剩余元素,直接加入 temp[]while (i <= mid) temp[k++] = q[i++];// 如果右区间还有剩余元素,直接加入 temp[]while (j <= r) temp[k++] = q[j++];// 将 temp[] 中的元素复制回原数组 q[]for (int i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];return res;  // 返回逆序对的数量
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> q[i];// 输出逆序对的数量cout << merge_sort(0, n - 1) << endl;return 0;
}

以上就是两种经典常考的排序算法,快排的思想是选择基准点,然后进行分区;而归并排序是选择一个位置,将原序列划分为两个序列,再分别进行排序,最后合并为一个有序数组。可以看到各有优缺点,下面进行一个简答的总结:
在这里插入图片描述

相关文章:

Acwing 排序

1.快速排序 主要思想&#xff1a;基于分治思想。通过选择一个基准元素&#xff0c;将数组分为两部分&#xff0c;左边部分元素都小于等于基准&#xff0c;右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。 分区逻辑&#xff1a;双指针算法 左指针i从左往右找…...

分布式环境下验证码登录的技术实现

分布式环境下验证码登录的技术实现 在分布式系统中&#xff0c;实现验证码登录是一个复杂但至关重要的任务。它不仅能防止暴力破解和自动化攻击&#xff0c;还能提高系统的安全性和用户体验。本文将详细介绍在分布式环境下如何实现验证码登录&#xff0c;涵盖验证码的生成、存…...

数据结构-5.9.树的存储结构

一.树的逻辑结构&#xff1a; 二.双亲表示法(顺序存储)&#xff1a; 1.树中除了根结点外每一颗树中的任意一个结点都只有一个父结点(双亲结点)&#xff1b; 2.结点包括结点数据和指针&#xff1b; 3.上述图片中右边的顺序存储解析&#xff1a;比如A结点左边的0&#xff0c;就…...

【Linux】解锁线程基本概念和线程控制,步入多线程学习的大门

目录 1、线程初识 1.1线程的概念 1.2.关于线程和进程的进一步理解 1.3.线程的设计理念 1.4.进程vs线程&#xff08;图解&#xff09; 1.5地址空间的第四谈 2.线程的控制&#xff1a; 2.1.关于线程控制的前置知识 2.2创建线程的系统调用&#xff1a; 这个几号手册具体…...

uniapp学习(005-2 详解Part.2)

零基础入门uniapp Vue3组合式API版本到咸虾米壁纸项目实战&#xff0c;开发打包微信小程序、抖音小程序、H5、安卓APP客户端等 总时长 23:40:00 共116P 此文章包含第41p-第p47的内容 文章目录 mainifest.json文件配置获取微信小程序appid注册微信小程序微信小程序控制台图形界…...

深度学习的关键概念和术语

特征 特征是图像上可进行视觉辨识的区域。特征通常代表对应用相关的内容&#xff08;缺陷、对象、对象的特定部分&#xff09;。 特征尺寸 仅用于聚焦模式下的绿色分类、红色、蓝色定位和蓝色读取工具。 您认为对分析图像内容最重要的图像特征的主观大小。该特征尺寸确定用于…...

navicate可视化数据库操作-cnblog

1 连接数据库 点击链接&#xff0c;自定义名称&#xff0c;输入root密码 2 准备按照图例创建数据库demo 3 新建数据库...

kubernetes中的微服务

目录 一 什么是微服务 二 微服务的类型 三 ipvs模式 3.1 ipvs模式配置方式 四 微服务类型详解 4.1 clusterip 4.2 ClusterIP中的特殊模式headless 4.3 nodeport 4.4 loadbalancer 4.5 metalLB 4.6 externalname 五 Ingress-nginx 5.1 ingress-nginx功能 5.2 部署…...

Python 量子机器学习及其应用

Python 量子机器学习及其应用 目录 &#x1f300; 量子机器学习的基础概念&#x1f4a1; 量子计算的原理与经典计算的区别&#x1f511; 量子算法在机器学习中的应用潜力⚛️ 量子计算与经典机器学习算法的结合&#x1f680; 案例展示&#xff1a;量子算法提升机器学习效率&a…...

echarts显示隐藏柱状图柱子的背景色

showBackground: true, //控制是否显示背景色backgroundStyle: {// color: rgba(180, 180, 180, 0.4) //背景色的颜色color: red} 关键代码是 showBackground: true, //控制是否显示背景色 设置为false或者直接而不写就是不显示背景色&#xff0c;默认是不显示背景色 true的时…...

QT文件操作【记事本】

mainwindow.h核心函数 QFileDialog::getOpenFileName()QFileDialog::getSaveFileName() #ifndef MAINWINDOW_H #define MAINWINDOW_H#include <QMainWindow> #include<QFileDialog> #include<QMessageBox> #include<QDebug> #include<QFile> #…...

Linux 定时备份系统日志

Linux 定时备份系统日志 SSH跨机免密登录复制备份到另一台虚机上开启定时任务 SSH跨机免密登录 定时备份首先要实现免登入 一、scp 一个文件从其他服务器到本机&#xff0c;怎么跳过ssh登录验证呢&#xff1f; 要在使用SCP时跳过密码登录&#xff0c;你可以设置SSH密钥认证。首…...

音视频入门基础:FLV专题(15)——Video Tag简介

一、引言 根据《video_file_format_spec_v10_1.pdf》第75页&#xff0c;如果某个Tag的Tag header中的TagType值为9&#xff0c;表示该Tag为Video Tag&#xff1a; 这时StreamID之后紧接着的就是VideoTagHeader&#xff0c;也就是说这时Tag header之后的就是VideoTagHeader&…...

尚硅谷rabbitmq2024 第15-18节 springboot整合与可靠性答疑

在spring boot项目中&#xff0c;只引入了一个amqp的starter&#xff0c;为什么在写listener的时候能看到rabbitmq相关的类&#xff0c;比如RabbitListener( public void processMessage(String dataString, Message message, channel channel){ 这里的Message就是rabbitmq下面…...

ctfshow-web 萌新题

给她 pyload: 1.dirsearch扫描&#xff0c;发现git 2. GitHack工具得到.git文件 <?php $passsprintf("and pass%s",addslashes($_GET[pass])); $sqlsprintf("select * from user where name%s $pass",addslashes($_GET[name])); ?>addslashes函…...

基于RPA+AI的网页自动填写机器人 | OPENAIGC开发者大赛高校组优秀作品

在第二届拯救者杯OPENAIGC开发者大赛中&#xff0c;涌现出一批技术突出、创意卓越的作品。为了让这些优秀项目被更多人看到&#xff0c;我们特意开设了优秀作品报道专栏&#xff0c;旨在展示其独特之处和开发者的精彩故事。 无论您是技术专家还是爱好者&#xff0c;希望能带给…...

Tmux常用操作--云GPU版

Tmux是什么&#xff0c;作用&#xff1f; Tmux是一个终端复用器&#xff08;terminal multiplexer&#xff09;&#xff0c;属于常用的开发工具。 作用 使用Tmux创建守护进程&#xff0c;可以使得关闭PyCharm或者其他终端的情况下&#xff0c;远程服务器&#xff08;云GPU&a…...

股市入门常见术语介绍

鉴于最近行情讨论火热&#xff0c;我也想借此平台&#xff0c;结合我大学时期身边同学老师的投资经历&#xff0c;写一篇交易入门术语简介。内容不多但是足以达到科普之用。 ​ 希望大家能谨慎对待投资&#xff0c;始终保持谦虚学习的态度。不要迷失在瞬息万变的金融市场&…...

专栏十九:单细胞大数据时代使用scvi和scanpy整合数据

慢更ing,主要是记录自己在分析中的一些困惑 一、基础知识和解惑 放在最前面,是因为scvi整合不像harmony,傻瓜式操作,很多地方还是要注意一下的。 1.如何正确的寻找HVGs 一般我们使用的函数就是scanpy.pp.highly_variable_genes,里面的参数较为复杂。 Q:输入数据的格…...

C语言编程必备知识

C语言是编程领域中基础且广泛使用的语言之一&#xff0c;掌握C语言编程需要一些核心知识&#xff0c;涵盖基本语法、内存管理、数据结构等方面。以下是C语言编程中的一些必备知识点&#xff1a; 1. **基础语法** - **变量声明**&#xff1a;所有变量都需要在使用前声明&…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...