给定有序表A[1:n] 修改合并排序算法，求出该有序表的逆序对数

137 阅读 0 评论 91 点赞

我是靠谱客的博主会撒娇方盒，这篇文章主要介绍给定有序表A[1:n] 修改合并排序算法，求出该有序表的逆序对数，现在分享给大家，希望可以做个参考。

有关逆序对数的概念：

定义：对于一个给定的数列,如果有i<j,且Ai>Aj,则称(i,j)为一逆序对.
要解决的问题是,给出一个数列,求出这个数列包含多少个逆序对。
例如，数组（3，1，4，5，2）的“逆序对”有<3,1>,《3,2》，<4,2><5,2>，共4个。

开始分析算法：

首先给定了这是一个有序表，所谓有序表，是指这样的线性表，其中所有元素以递增或递减方式有序排列。
所以我们不用再进行排序了。
一般思路，就是就是遍历整个序列，判断实数与它后面的每个实数是否构成逆序对，这种算法的时间复杂度为Ο(n2)。
另一种就是采用分治算法，分为小规模的算法，进行分析。
下面上代码，直接进行边看边讲解：‘

package hello;

import org.omg.CORBA.PUBLIC_MEMBER;

public class M2 {
   
	public static int n=0;
	public static void merge(int a[],int first,int mid,int last)
	{
   
	int temp[] = new int[last-first+1