1、归并排序&逆序对数量

AcWing 787. 归并排序

AcWing 788. 逆序对的数量

import java.util.*;

//归并排序
//ACWing
public class Main {
    public static void main(String[] args) {
        // 对输入值进行初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        // 归并排序
        merge_sort(arr, 0, n - 1);

        // 打印输出
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    // 归并排序
    private static void merge_sort(int[] arr, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(arr, l, mid);
        merge_sort(arr, mid + 1, r);

        int[] tmp = new int[r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];
        for (k = 0, i = l; k < tmp.length; k++, i++)
            arr[i] = tmp[k];
    }
}




//逆序对数量，归并的思路
import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        // 对输入值进行初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        // 归并排序
        long res=merge_sort(arr, 0, n - 1);

        System.out.println(res);
    }

    // 归并排序
    private static long merge_sort(int[] arr, int l, int r) {
        long res = 0;
        if (l >= r) return 0;
        int mid = (l + r) / 2;
        res += merge_sort(arr, l, mid);
        res += merge_sort(arr, mid + 1, r);

        int[] tmp = new int[r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= r) tmp[k++] = arr[j++];
        for(j=l,i=mid+1;j<=mid&&i<=r;i++){
            while(j<=mid&&arr[j]<=arr[i])
                j++;
            res+=mid-j+1;
            j=l;
        }
        for (k = 0, i = l; k < tmp.length; k++, i++)
            arr[i] = tmp[k];
        return res;
    }
}