欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组的逆序对个数

程序员文章站 2022-05-10 15:33:12
...

计算数组的逆序对个数
如果按照升序为准,如果数组已经按照升序排列,则逆序对个数为0;若数组是降序排列的,则逆序对个数最多。
可以使用归并排序解决

	public void sort(int[] n,int start,int end,int[] t){
	    //计算数组的中间位置
	    int mid = start + (end - start) / 2;
	    if(start < end){
	        //前半段排序
	    	sort(n,start,mid,t);
	    	//后半段排序
	    	sort(n,mid+1,end,t);
	    	//合并
	    	merge(n,start,mid,end,t);
	    }

	}
	static void merge(int[] n,int start,int mid,int end,int[] t){
		int[] tmp = new int[end - start + 1];
		int i = start;
		int j = mid+1;
		int k = 0;
		//遍历前后数组,并进行排序,将排序结果保存在临时数组中
		while(i <= mid && j <= end){
			if(n[i] > n[j]){
				tmp[k++] = n[j++];
				t[0] += (mid + 1 - i);
			} else {
				tmp[k++] = n[i++];
			}
		}
		//将左边剩余数加到临时数组
		while(i <= mid){
			tmp[k++] = n[i++];
		}
		//将右边剩余数加到临时数组
		while(j <= end){
			tmp[k++] = n[j++];
		}
		//将临时数组的内容覆盖原来数组的内容
		for(int m=0; m<tmp.length; m++){
			n[m+start] = tmp[m];
		}
	}
	//测试案例
	public static void main(String[] args){
	    int[] d = new int[]{1,5,7,9,3,2};
	    int[] t = new int[1];
	    sort(d,0,5,t);
	}