首页 > 其他分享 >归并排序

归并排序

时间:2023-01-29 16:02:50浏览次数:40  
标签:归并 int 元素 mid 排序 逆序

归并排序的思路

1.将整个区间分为两个子区间
即[L , R]=> [L , mid] + [mid + 1 , R]
2.递归排序[L , mid] 和 [mid + 1 , R]
3.归并,将左右两个有序序列合并为一个有序序列

归并排序模板

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;//定义mid将区间分为两个子区间
    merge_sort(q, l, mid);//递归排序左右两个子区间
    merge_sort(q, mid + 1, r);
    //归并,将排好序的数字放入临时数组tmp
    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 ++ ];
   //扫尾,剩余的数据直接放入tmp数组
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];
   //将排好序的序列放回原数组q
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

AcWing 788. 逆序对的数量

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

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

输入格式

第一行包含整数 n ,表示数列的长度。
第二行包含 n 个整数,表示整个数列。

输出格式

输出逆序对的个数。

数据范围

1≤n≤100000
数列中的元素的取值范围 [1,1000000000](注意数据范围,数据类型应该定义为long long)

输入样例:

6
2 3 4 5 6 1

输出样例:

5

解题思路

将序列从中间分开,将逆序对分成三类:

1.两个元素都在左边;
2.两个元素都在右边;
3.两个元素一个在左一个在右;
因此这就是我们算法的大致框架:

计算逆序对的数量(序列):
1.递归算左边的;
2.递归算右边的;
3.算一个左一个右的;
4.把他们加到到一起;

这个时候我们注意到一个很重要的性质,左右半边的元素在各自任意调换顺序,是不影响第三步计数的,因此我们可以数完就给它排序。这么做的好处在于,如果序列是有序的,会让第三步计数很容易。如果无序暴力数的话这一步是O(n^2)的。

比如序列是这样的
4 5 6 | 1 2 3
当你发现 4 比 3 大的时候,也就是说右边最大的元素都小于左边最小的元素,那么左边剩下的5和6都必然比右边的所有元素大,因此就可以不用数5和6的情形了,直接分别加上右半边的元素个数就可以了,这一步就降低到了O(n)

代码

#include <iostream>

using namespace std ;
const int N = 1e6+10 ;
int n ;
int q[N] , tmp[N];

long long merge_sort(int l ,int r )
{
	if(l==r) return 0;
	int mid = (l + r ) <<1 ; //定义mid分为左右两段,"<<1"右移一相当于整除二 
	long long res = merge_sort(l , mid) + merge_sort(mid +1 , r) ;
	//定义res储存逆序对数量 
	//先处理前两种情况,即两个数都在左边和都在右边 
	
	//归并的过程 
	int k = 0 , i = l , j = mid + 1 ;//讨论第三种情况,即两个数在左右两边 
	while(i<=mid&&j<=r)
	{
		if(q[i]<q[j]) tmp[++k]=q[++i];//将排好序的数字放入临时数组tmp当中 
		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 =1 , j=0 ; i<r;i++ , j++) q[i]=tmp[j];
		return res ;
}
int main ()
{
	cin>>n;
	for(int i=0 ;i<n ;i++) scanf("%d",&q[i]);
	
	cout<<merge_sort(0 , n-1)<<endl; //从0到n-1递归排序 直接输出结果 
	return 0;
}

标签:归并,int,元素,mid,排序,逆序
From: https://www.cnblogs.com/wustRen/p/17072909.html

相关文章

  • 力扣-82-删除排序链表中的重复元素Ⅱ
    这个删除重复不太常规的是:它不是删除多出来的剩下一个,而是比如有三个1,1重复了,那这三个1节点都不要 ListNode*deleteDuplicates(ListNode*head){ if(!head)returnh......
  • 17种编程语言实现排序算法-桶排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 17种编程语言实现排序算法-计数排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 17种编程语言+10种排序算法
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 17种编程语言实现排序算法-堆排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 17种编程语言实现排序算法-插入排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 17种编程语言实现排序算法-合并排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • Arrays.sort()降序排序
    默认的Java.util包中的Arrays.sort(),可以实现对java中的基本数据类型(byte、char、short、int、long、float、double、boolean)的数组进行升序排序。但如果要实现降序排列,则......
  • 17种编程语言实现排序算法-选择排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift......
  • 17种编程语言实现排序算法-冒泡排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......