排序---P1116 车厢重组

P1116 车厢重组

来自 <车厢重组 - 洛谷>

其实这道题本质上就是求逆序对的过程：

两种方法：一个是通过冒泡排序过程求逆序对；一个是通过归并排序过程求逆序对。

法一：当通过冒泡排序进行正序排列时，相邻两个数需要进行交换时，则说明这是一个逆序对，逆序对++。

import java.util.Scanner;
 
 
 
/**
 * 用冒泡思想算逆序对，每次进行交换时，逆序对++
 */
 
public class Main {
 
    public static void main(String[] args) {
 
        int n,ans=0;
 
        Scanner scanner=new Scanner(System.in);
 
        n = scanner.nextInt();
 
        int[] a=new int[n];
 
        for(int i=0;i
 
            a[i]=scanner.nextInt();
 
        }
 
        for(int i=1;i<=n-1;i++){
 
            for(int j=0;j<=n-1-i;j++){
 
                if(a[j]>a[j+1]){
 
                    int t=a[j];
 
                    a[j]=a[j+1];
 
                    a[j+1]=t;
 
                    ans++;
 
                }
 
            }
 
        }
 
        System.out.println(ans);
 
    }
 
}

法二：归并排序，逆序对=左边有序数列的逆序对+右边有序数列的逆序对+处于左右两边的逆序对

 

import java.util.Scanner;
 
 
 
/**
 * 用归并的思路算逆序对
 */
 
public class Main {
 
    public static int n;
 
    public static int[] a=new int[100005];
 
    public static int[] temp=new int[100005];
 
    public static void main(String[] args) {
 
        Scanner scanner=new Scanner(System.in);
 
        n=scanner.nextInt();
 
        for(int i=0;i
 
            a[i]=scanner.nextInt();
 
        }
 
        System.out.println(merge_sort(0,n-1));
 
    }
 
    public static int merge_sort(int l,int r){
 
        if(l>=r){
 
            return 0;
 
        }
 
        int mid=(l+r)/2;
 
        int res=merge_sort(l,mid)+merge_sort(mid+1,r);
 
        int i=l,j=mid+1,k=0;
 
        while(i<=mid&&j<=r){
 
            if(a[i]<=a[j]){
 
                temp[k++]=a[i++];
 
            }
 
            else{
 
                res+=mid-i+1;
 
                temp[k++]=a[j++];
 
            }
 
        }
 
        while(i<=mid){
 
            temp[k++]=a[i++];
 
        }
 
        while (j<=r){
 
            temp[k++]=a[j++];
 
        }
 
        for(i=l,j=0;i<=r;i++,j++){
 
            a[i]=temp[j];
 
        }
 
        return res;
 
    }
 
}