采用归并排序思想解决逆序对数问题

秒速五厘米 2022-06-18 11:20 179阅读 0赞

//归并排序解逆序对数问题
    public class MergeSort {
    	static int count=0;
    	
    	public static void mergeSort(int[] arr,int p,int r)
    	{
    		if (p<r)
    		{
    			int q=(p+r)/2;
    			mergeSort(arr,p,q);
    			mergeSort(arr,q+1,r);
    			merge(arr,p,q,r);
    		}
    	}
    
    	public static void merge(int[] arr,int p,int q,int r)
    	{
    		int n1=q-p+1;
    		int n2=r-q;
    		int[] arrL=new int[n1+1];
    		int[] arrR=new int[n2+1];
    
    		for (int i=0;i<n1 ;i++ )
    		{
    			arrL[i]=arr[p+i];
    		}
    		for (int j=0;j<n2 ;j++ )
    		{
    			arrR[j]=arr[q+j+1];
    		}
    		arrL[n1]=65535;
    		arrR[n2]=65535;
    
    		int x=0,y=0;
    		for (int k=p;k<=r ;k++ )
    		{
    			if (arrL[x]<=arrR[y])
    			{
    				arr[k]=arrL[x];
    				x++;
    			}else
    			{
    				arr[k]=arrR[y];
    				count=count+n1-x;//若arrL[x]>arrR[y]，arrL中大于等于arrL[x]的数都比arrR[y]大，都与arrR[y]是逆序对
    				
    				for (int m=x;m<n1 ;m++ )
    				{
    					System.out.println("["+arrL[m]+","+arrR[y]+"]");
    				}
    
    				y++;
    			}
    		}
    	}
    
    	public static void main(String[] args) 
    	{
    		int[] arr={2,3,8,6,1};
    		mergeSort(arr,0,arr.length-1);
    		System.out.println("count:"+count);
    	}
    }
    
    [6,1]
    [2,1]
    [3,1]
    [8,1]
    [8,6]
    count:5

发表评论取消回复

表情：

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

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

相关阅读

相关计算逆序对数

计算逆序对数数学术语逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i

冷不防/ 2024年03月31日 13:11/ 0 赞/ 67 阅读

相关【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）

![89b44368cd4c4d1082a6fbc2ec9980bc.png][] 目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、归并排序思想 2.

小咪咪/ 2023年10月16日 17:45/ 0 赞/ 6 阅读

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

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

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

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

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

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

相关【模板】——求序列逆序对数

用归并排序 ll MergeSort(int s[], int left, int middle, int right) { int i =

Love The Way You Lie/ 2022年09月01日 14:45/ 0 赞/ 144 阅读

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

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

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

相关采用归并排序思想解决逆序对数问题

//归并排序解逆序对数问题 public class MergeSort { static int count=0; publi

秒速五厘米/ 2022年06月18日 11:20/ 0 赞/ 180 阅读

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

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

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

相关逆序数问题使用归并排序

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如3 4 1 2这个数组有

忘是亡心i/ 2022年04月17日 05:39/ 0 赞/ 237 阅读

相关【搞定算法】归并排序及其解决逆序对数、小和问题

归并排序也是分治法一个很好的应用，先递归到最底层，然后从下往上每次两个序列进行归并合起来，是一个由上往下分开，再由下往上合并的过程。而对于每一次合并操作，对于每一次 mer

电玩女神/ 2021年12月14日 03:49/ 0 赞/ 218 阅读