排序---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<n;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<n;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;     } }