【算法】快速排序与归并排序
admin
2024-02-04 02:22:09
0次

一，快速排序

1.1模板

void quick_sort(int q[], int l, int r) {if (l >= r)return;int x = q[l], i = l - 1, j = r + 1;while (i < j) {doi++;while (q[i] < x);doj--;while (q[j] > x);if (i < j)swap(q[i], q[j]);elsebreak;}quick_sort(q, l, j);quick_sort(q, j + 1, r);//如果这里是i的话那么填空i-1，i。x不能取q[l]和q[(l+r)>>1]，否则会出现边界问题。//如果这里是j的话那么填空j，j+1。x不能取q[r]和q[(l+r+1)>>1]，否则会出现边界问题。
}

1.2题目：第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1-10^9 范围内），表示整数数列。

输出格式

输出一个整数，表示数列的第 k 小数。

数据范围

1<=n<=100000

1<=k<=n

输入样例

5 3
2 4 1 5 3

输出样例

3

AC代码

#include using namespace std;int N[100010];void quick_sort(int q[],int l,int r){if(l>=r)return;int x=q[l],i=l-1,j=r+1;while(ix);if(i>1]//当这里为i的时候则填i-1和i。x则不能为q[l]和q[(r+l)>>1]
}int main(){int n,k;cin>>n>>k;for(int i=0;i>N[i];quick_sort(N,0,n-1);cout<

二，归并排序

1.1模板

int tmp[N];
void merge_sort(int q[],int l,int r){if(l>=r)return;int mid=l+r>>1;//递归merge_sort(q,l,mid),merge_sort(q,mid+1,r);int k=0,i=l,j=mid+1;//归并的过程while(i<=mid&&j<=r)if(q[i]

1.2题目：逆序对的数量

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i个和第 j 个元素，如果满足 i 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1<=n<=100000，

数列中的元素的取值范围[1,10^9]。

输入样例

6
2 3 4 5 6 1

输出样例

5

AC代码

#include using namespace std;int q[100010],tmp[100010];
typedef long long LL;LL merge_sort(int l,int r){if(l>=r)return 0;int mid=l+r>>1;LL res=merge_sort(l,mid)+merge_sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(q[i]<=q[j])tmp[k++]=q[i++];else{tmp[k++]=q[j++];res+=mid-i+1;}}while(i<=mid)tmp[k++]=q[i++];while(j<=r)tmp[k++]=q[j++];for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];return res;
}int main(){int n;cin>>n;for(int i=0;i>q[i];cout<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：物联网安全年报信息采集

下一篇：一文带你搞懂sklearn.metrics混淆矩阵

相关内容

热门资讯

【MySQL】锁 锁 文章目录锁全局锁表级锁表锁元数据锁（MDL）意向锁AUTO-INC锁...
【内网安全】 隧道搭建穿透上线... 文章目录内网穿透-Ngrok-入门-上线1、服务端配置：2、客户端连接服务端ÿ...
GCN的几种模型复现笔记 引言 本篇笔记紧接上文，主要是上一篇看写了快2w字，再去接入代码感觉有点...
数据分页展示逻辑 import java.util.Arrays;import java.util.List;impo...
Redis为什么选择单线程？R... 目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程？三、R...
【已解决】ERROR: Cou... 正确指令： pip install pyyaml
关于测试，我发现了哪些新大陆 关于测试 平常也只是听说过一些关于测试的术语，但并没有使用过测试工具。偶然看到编程老师...
Lock 接口解读 前置知识点Synchronized synchronized 是 Java 中的关键字，...
Win7 专业版安装中文包、汉... 参考资料：http://www.metsky.com/archives/350.htm...
3 ROS1通讯编程提高(1) 3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...
大模型未来趋势 大模型是人工智能领域的重要发展趋势之一，未来有着广阔的应用前景和发展空间。以下是大模型未来的趋势和展...
python实战应用讲解-【n... 目录 如何在Python中计算残余的平方和 方法1：使用其Base公式 方法2：使用statsmod...
学习u-boot 需要了解的m... 一、常用函数 1. origin 函数 origin 函数的返回值就是变量来源。使用格式如下...
常用python爬虫库介绍与简... 通用 urllib -网络库(stdlib)。 requests -网络库。 grab – 网络库&...
药品批准文号查询|药融云-中国... 药品批文是国家食品药品监督管理局（NMPA）对药品的审评和批准的证明文件...
【2023-03-22】SRS... 【2023-03-22】SRS推流搭配FFmpeg实现目标检测 说明： 外侧测试使用SRS播放器测...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
初级算法-哈希表 主要记录算法和数据结构学习笔记，新的一年更上一层楼！ 初级算法-哈希表...
进程间通信【Linux】 1. 进程间通信 1.1 什么是进程间通信 在 Linux 系统中，进程间通信...
【Docker】P3 Dock... Docker数据卷、宿主机与挂载数据卷的概念及作用挂载宿主机配置数据卷挂载操作示例一个容器挂载多个目...