排序---逆序对

喜欢ヅ旅行 2022-02-23 09:34 213阅读 0赞

题目：[https://www.acwing.com/problem/content/description/109/][https_www.acwing.com_problem_content_description_109]

在进行冒泡排序的同时也就是在进行求逆序队的操作  但是复杂度较高O(n2) 级别

利用归并排序可以将复杂度降至O(nlogn)级别

更有趣的是  在进行归并排序时在归并的时候

我们对于两个子序列求逆序对数（递归推出这两个子序列一定是有序的）

例：

4     5    8

3     7    9

归并   i，j指针分别指向这两个子序列的开头

i==1 ,j==1 时   如果a\[i\]>a\[j\]   就一定存在 a\[i\]~a\[mid\]  都大于a\[j\]   这样逆序对=mid-i+1;

所以  AC代码

#include<iostream>
    #define N 500010
    #define ll long long
    using namespace std;
    ll n,ans=0;
    ll a[N],b[N]; 
    void meger(ll a[],ll l,ll r){
    	if(r-l<1) return;
    	ll mid=(l+r)>>1;
    	meger(a,l,mid);
    	meger(a,mid+1,r);
    	ll i=l,j=mid+1;
    	for(int k=l;k<=r;k++){
    		if(j>r || i<=mid&&a[i]<a[j]) b[k]=a[i++];
    		else {
    			b[k]=a[j++];
    			ans+=mid-i+1;
    		}
    	}
    	for(int k=l;k<=r;k++){
    	   a[k]=b[k];	
    	}
    }
    
    int main(){
    	while(cin>>n && n){
    		ans=0;
    	for(ll i=1;i<=n;i++)
    	cin>>a[i];
    	
    	meger(a,1,n);
    	
    	cout<<ans<<endl;
        }
    	return 0;
    	
    }

[https_www.acwing.com_problem_content_description_109]: https://www.acwing.com/problem/content/description/109/

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序 AcWing 788. 逆序对的数量

归并排序 AcWing 788. 逆序对的数量原题链接 [AcWing 788. 逆序对的数量][AcWing 788.] 算法标签归并排序思路

小鱼儿/ 2023年09月28日 11:09/ 0 赞/ 115 阅读

相关 P1908 逆序对 (归并排序实现)

题目描述 > 猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之

朱雀/ 2023年05月29日 11:56/ 0 赞/ 215 阅读

相关数组中的逆序对（归并排序思想）

利用归并排序思想这题没有看懂，转来暂存 ![aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vZmlsZXMvMjAxODA1M

心已赠人/ 2023年01月02日 06:23/ 0 赞/ 193 阅读

相关 1013 逆序对

Description 给定一个长度为N的int型数组a[0,1,2,...N-1], 请计算逆序对个数.当i<j且a[i]>a[j], 则称a[i]与a[j]是一对

墨蓝/ 2022年09月11日 15:21/ 0 赞/ 164 阅读

相关利用归并排序求逆序对

在逆序对的问题中，如果采用暴力求解的方法，一般也是有效的，但是O(n2)时间复杂度实在是难以接受的。但是对于逆序对问题，却有一个看似不想关的算法来解决–归并排序。时间复杂度和空

以你之姓@/ 2022年08月04日 15:40/ 0 赞/ 184 阅读

相关归并排序之数组的逆序对

题意：求出给定的数组中的逆序对的数量，可使用归并排序求解。 import java.util. ; public class Solution {

小灰灰/ 2022年08月04日 10:41/ 0 赞/ 167 阅读

相关数据结构：归并排序 && 逆序对统计

归并排序要注意归并排序需要一个辅助空间，别的直接递归即可代码如下 include <iostream> include <vector>

╰半夏微凉°/ 2022年05月31日 12:53/ 0 赞/ 188 阅读

相关逆序对 - 超快速排序

在这个问题中，您必须分析特定的排序算法----超快速排序。该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。对于输入序列9 1 0 5 4，

我不是女神ヾ/ 2022年03月20日 05:58/ 0 赞/ 189 阅读

相关排序---逆序对

题目：[https://www.acwing.com/problem/content/description/109/][https_www.acwing.com_proble

喜欢ヅ旅行/ 2022年02月23日 09:34/ 0 赞/ 214 阅读

相关逆序对个数

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的

蔚落/ 2022年01月30日 08:21/ 0 赞/ 229 阅读