一、基础算法2：归并排序模板题+算法模板（归并排序，求逆序对的数量）

超、凢脫俗 2023-10-08 20:52 47阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  归并排序算法模板
     *  求逆序对的数量模板
 *  模板题
 *   *  归并排序
     *   *  原题链接
         *  题目
         *  题解
     *  求逆序对的数量
     *   *  原题链接
         *  题目
         *  题解

## 算法模板 ##

### 归并排序算法模板 ###

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]<=q[j]) tmp[k++] = q[i++];
    		else tmp[k++] = q[j++];
    	}
    	
    	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];		
    }

### 求逆序对的数量模板 ###

typedef long long LL;
    LL merge_cnt(int l,int r){
        
    	if(l>=r) return 0;
    	
    	int mid = l+r >> 1;
    	LL res = merge_cnt(l,mid) + merge_cnt(mid+1,r); //注意要用LL(long long，不然会爆int） 
    	
    	//归并的过程 
    	int k = 0, i = l ,j = mid+1;
    	while(i<=mid && j<=r){
        
    		if(q[i]<=q[j]) tmp[k++] = q[i++];
    		else{
        
    			tmp[k++] = q[j++];
    			res += mid-i+1; 
    			// “局部有序”，所以当q[i]>q[j]时，q[i]~q[mid]都>g[i],所以Sj=mid-i+1
    		}
    	} 
    	
    //	扫尾 
    	while(i<=mid) tmp[k++] = q[i++];
    	while(j<=r) tmp[k++] = q[j++];
    	
    //	物归原主 
    	for(int i=l,j=0;i<=r;i++,j++) q[i] = tmp[j];
    	
    	return res;
    }

无注释简洁版

typedef long long LL;
    LL merge_cnt(int l,int r){
        
    	if(l>=r) return 0;
    	
    	int mid = l+r >> 1;
    	LL res = merge_cnt(l,mid) + merge_cnt(mid+1,r);
    	
    	int k = 0, i = l ,j = mid+1;
    	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(int i=l,j=0;i<=r;i++,j++) q[i] = tmp[j];
    	return res;
    }

## 模板题 ##

### 归并排序 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/789/][https_www.acwing.com_problem_content_789]

#### 题目 ####

787 . 归并排序  
给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式  
输入共两行，第一行包含整数 n。

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

输出格式  
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围  
1≤n≤100000  
输入样例：

5
    3 1 2 4 5

输出样例：

1 2 3 4 5

#### 题解 ####

#include <iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int n;
    int q[N],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]<=q[j]) tmp[k++] = q[i++];
    		else tmp[k++] = q[j++];
    	}
    	
    	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];		
    }
    
    
    int main(){
        
    	scanf("%d",&n);
    	
    	for(int i=0;i<n;i++) scanf("%d",&q[i]);
    	
    	merge_sort(q,0,n-1);
    	
    	for(int i=0;i<n;i++) printf("%d ",q[i]);
    	
    	return 0;
    }

![在这里插入图片描述][bfaf9d95b45c4cf4a236c82c7206c2f6.png]

### 求逆序对的数量 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/790/][https_www.acwing.com_problem_content_790]

#### 题目 ####

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

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

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

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

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

数据范围  
1≤n≤100000，  
数列中的元素的取值范围 \[1,109\]。

输入样例：

6
    2 3 4 5 6 1

输出样例：

#### 题解 ####

#include <iostream>
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1e6 + 10;
    
    int n;
    int q[N],tmp[N];
    
    LL merge_cnt(int l,int r){
        
    	if(l>=r) return 0;
    	
    	int mid = l+r >> 1;
    	LL res = merge_cnt(l,mid) + merge_cnt(mid+1,r); //注意要用LL(long long，不然会爆int） 
    	
    	//归并的过程 
    	int k = 0, i = l ,j = mid+1;
    	while(i<=mid && j<=r){
        
    		if(q[i]<=q[j]) tmp[k++] = q[i++];
    		else{
        
    			tmp[k++] = q[j++];
    			res += mid-i+1; 
    			// “局部有序”，所以当q[i]>q[j]时，q[i]~q[mid]都>g[i],所以Sj=mid-i+1
    		}
    	} 
    	
    //	扫尾 
    	while(i<=mid) tmp[k++] = q[i++];
    	while(j<=r) tmp[k++] = q[j++];
    	
    //	物归原主 
    	for(int i=l,j=0;i<=r;i++,j++) q[i] = tmp[j];
    	
    	return res;
    }
    int main(){
        
    	scanf("%d",&n);
    	
    	for(int i=0;i<n;i++) cin>>q[i];
    	
    	cout<<merge_cnt(0,n-1);
    	
    	return 0;
    }

![在这里插入图片描述][6f4d656d791e460db9b7e642d09e1dd4.png]  
![在这里插入图片描述][cbc550387038404ba40be9c6f84f69df.png]  
![在这里插入图片描述][f913524aa8594bffb060309e2f89dd67.png]

[https_www.acwing.com_problem_content_789]: https://www.acwing.com/problem/content/789/
[bfaf9d95b45c4cf4a236c82c7206c2f6.png]: https://img-blog.csdnimg.cn/bfaf9d95b45c4cf4a236c82c7206c2f6.png
[https_www.acwing.com_problem_content_790]: https://www.acwing.com/problem/content/790/
[6f4d656d791e460db9b7e642d09e1dd4.png]: https://img-blog.csdnimg.cn/6f4d656d791e460db9b7e642d09e1dd4.png
[cbc550387038404ba40be9c6f84f69df.png]: https://img-blog.csdnimg.cn/cbc550387038404ba40be9c6f84f69df.png
[f913524aa8594bffb060309e2f89dd67.png]: https://img-blog.csdnimg.cn/f913524aa8594bffb060309e2f89dd67.png