专栏首页ypw用归并排序求逆序对数(包括归并排序算法实现及代码)

用归并排序求逆序对数(包括归并排序算法实现及代码)

在算法设计课上老师给出了如上一个问题,让用刚学习的归并排序算法来实现求逆序对数。

那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

所谓归并排序算法,就是采用分治法将问题规模不断缩小,然后在合并的一个过程。 假设有一个数组,那么我们是一直将其划分,直到只剩余一个元素,那么这个时候我们往回合并,合并过程很简单,无非是每两个数组指针动不动,具体图解如下:

那么我们用代码实现如下:

#include<bits/stdc++.h>
#define maxn 10005
using namespace std;

int a[maxn];

//归并过程
void merge(int arr[], int l, int mid, int r){
	int help[r-l+1];//辅助数组
	int i = 0;
	int lIndex = l;
	int rIndex = mid+1;
	while(lIndex <= mid && rIndex <= r){
		help[i++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++]:arr[rIndex++];	
	}
    //左边和右边肯定有一边到头了,不可能同时,因为每次只移动一边
	while(lIndex <= mid){
		help[i++] = arr[lIndex++];
	} 
	while(rIndex <= r){
		help[i++] = arr[rIndex++];
	}
    //将排好序的辅助数组赋值给原始数组,不需要返回值
	for(i = 0; i < r-l+1; i++){
		arr[l+i] = help[i];
	}
}
 
//递归
void mergeSort(int arr[], int l, int r){
	if(l == r){
		return;
	}
	int mid = (l + r) / 2;
    //左半部分归并排序
	mergeSort(arr, l, mid);
    //右半部分归并排序
	mergeSort(arr, mid+1, r);
    //左右部分归并
	merge(arr, l, mid, r);
}
 
//归并排序整个数组
void mergeSort(int arr[], int n){//特判,如果数组为空或只有一个元素,那么就不需要排序
	if(arr == NULL || n < 2){
		return;
	}
	mergeSort(arr,0,n-1);
}

int main(){
	int n; 
	while(cin >> n){
		for(int i = 0; i < n; i++) 
		cin >> a[i];
 
		mergeSort(a, n);
 
		for(int i = 0; i < n; i++){
			cout << a[i] << " ";
		} 
		cout << endl;
	}
	return 0;
} 

那么在实现并掌握归并排序算法的基础上,我们只要对其做一点修改就能满足题目的要求了。 注:为了增强可读性,让老师运行一下,我加了几行说明;

/*
采用归并排序求逆序对数
测试数据:
5
1 2 3 4 5    0

5
5 4 3 2 1  10 
*/
#include<bits/stdc++.h>
#define maxn 10005
using namespace std;

int n;//输入数据的个数 
int tot;//用于计数求逆序对的个数 
int a[maxn];//用于存放数据个数 
int b[maxn];//存放 
 
void mersort(int l, int r){
	if(l>=r) return ;
	int midd = (l+r)/2;
	int i = l;
	int j = midd+1;
	int k = 0;
	while(i<=midd&&j<=r){
		if(a[i] > a[j]){
			b[k++] = a[j++];
			tot += midd-i+1; 
		}else{
			b[k++] = a[i++];
		}
	}
	while(i<=midd) b[k++] = a[i++];
	while(j<=r) b[k++] = a[j++];
	for(int i=0;i<k;i++) a[i+l] = b[i];
}

void mer(int l,int r){
	if(l>=r) return ;//超过则返回
	
	int mid = (l+r)/2; //不断划分 
	mer(l,mid);
	mer(mid+1,r);
	
	mersort(l,r);//合并 
}

int main(){
	cout<<"请输入数据的个数:"<<endl;
	cin>>n;
	cout<<"请输入数据,各数据间用空格隔开"<<endl;
	for(int i=0;i<n;i++)
	 cin>>a[i]; 
	tot = 0;//初始化为0 
	mer(0,n-1);
	cout<<"逆序对个数为:"<<endl; 
	cout<<tot<<endl; 
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 回溯法求组合问题

    用户7727433
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    用户7727433
  • BZOJ2434: [Noi2011]阿狸的打字机(AC自动机 树状数组)

    attack
  • 一遍记住Java常用的八种排序算法与代码实现

    对Java技术,架构技术感兴趣的同学,欢迎加QQ群668041364,一起学习,相互讨论。 群内已经有小伙伴将知识体系整理好(源码,笔记,PPT,学习视频),欢...

    java爱好者
  • C++ 函数指针的定义方法及使用

    第一种,c语言通用。定义一个process_job函数指针类型,返回值为 int ,函数参数为int a,int b。使用用两种方法。

    forxtz
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • loj#6436. 「PKUSC2018」神仙的游戏(生成函数)

    我们考虑枚举一个长度len。有一个结论是如果我们按N - len的余数分类,若同一组内的全为0或全为1(?不算),那么存在一个长度为len的border。

    attack

扫码关注云+社区

领取腾讯云代金券