【java】归并排序 逆序对数归并排序逆序对数

归并排序

按照分治三步法，介绍归并排序步骤：

划分问题：把序列分成元素个数尽量相等的两半；

递归求解：把两半元素分别排序；

合并问题：把两个有序表合并成一个。

前两部分容易完成，关键在于如何合并问题。

归并排序代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void mergeSort(int[] arr,int x,int y,int []temp){
		if(y-x<=1)
			return;
		int m=(x+y)/2;
		mergeSort(arr,x,m,temp);
		mergeSort(arr,m,y,temp);
		int index=x,p=x,q=m;
		while(p<m||q<y){
			if(p>=m){
				temp[index++]=arr[q++];
			}else if(q>=y){
				temp[index++]=arr[p++];
			}else if(arr[p]<=arr[q]){
				temp[index++]=arr[p++];
			}else{
				temp[index++]=arr[q++];
			}
		}
		for(int i=x;i<y;i++){	//将辅助空间的有序元素复制回去
			arr[i]=temp[i];
		}
	}
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext())
		{
			int n=scanner.nextInt();
			int[] arr=new int[n];
			int[] temp=new int[n];	//申请的辅助空间
			for(int i=0;i<n;i++){
				arr[i]=scanner.nextInt();
			}
			mergeSort(arr,0,n,temp);
			System.out.println(Arrays.toString(arr));
		}
		scanner.close();
	}
}

逆序对数

import java.util.Scanner;

public class Main {
	public static int mergeSort(int[] arr,int x,int y,int []temp){
		if(y-x<=1)
			return 0;
		int m=(x+y)/2;
		int left=mergeSort(arr,x,m,temp);
		int right=mergeSort(arr,m,y,temp);
		int index=x,p=x,q=m;
		int count=0;
		while(p<m||q<y){
			if(p>=m){
				temp[index++]=arr[q++];
			}else if(q>=y){
				temp[index++]=arr[p++];
			}else if(arr[p]<=arr[q]){
				temp[index++]=arr[p++];
			}else{
				temp[index++]=arr[q++];
				count+=(m-p);
			}
		}
		for(int i=x;i<y;i++){
			arr[i]=temp[i];
		}
		return count+left+right;
	}
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext())
		{
			int n=scanner.nextInt();
			int[] arr=new int[n];
			int[] temp=new int[n];
			for(int i=0;i<n;i++){
				arr[i]=scanner.nextInt();
			}
			System.out.println(mergeSort(arr,0,n,temp));
		}
		scanner.close();
	}
}

最后

以上就是动人台灯为你收集整理的【java】归并排序 逆序对数归并排序逆序对数的全部内容，希望文章能够帮你解决【java】归并排序 逆序对数归并排序逆序对数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。