引理:逆序数
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
该排列的逆序数等于该排列转化为自然排序(从小到大)的最小次数
例如:31425 的逆序数为3
-
3无逆序,则n1 = 0,
-
1逆序有3,则n2 = 1,
-
4无逆序,则n3 = 0,
-
2逆序有3,4,则n4 = 2,
-
5无逆序,则n5 = 0,
-
若将该序列转化成从小到大排序,需要(n1 + n2 + n3 + n4 + n5)次交换。
直接计算
计算一个排列的逆序数的直接方法是逐个枚举逆序,同时统计个数。例如在序列 { 3, 1, 4, 2, 5 } 中,逆序依次为 (3,1),(3,2),(4,3),因此该序列的逆序数为 3。
归并排序
直接计数法虽然简单直观,但是其时间复杂度是O(n^2)
。一个更快的计算方法是在归并排序的同时计算逆序数。且该方法只是交换相邻的两个元素,符合题意。
算法分析
(归并排序)
-
给定两个有序序列,从右边序列中最小的元素开始往左边序列中插入,设右边序列中选定的元素的位置为j,左边序列选定的元素位置为i,中间位置为mid,则此时交换的位置次数是(mid - i + 1),最后把所有归并后交换的次数累加在一起即可。
-
例如 31425 经过归并后得出两个有序序列 134 和 25 (注意:314也是需要归并交换位置得到123的)即将2 插入到3位置前,此操作相当于交换了两次位置,设3元素的位置为i,4元素的位置是中间位置mid,则此时交换的次数为(mid - i + 1) = 2次
附上主播的图
时间复杂度$O(nlogn)$
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static long count = 0;
static long[] arr = new long[500010];
public static void merge_sort(long q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
long[] tmp = new long[r - l + 1];
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] > q[j]) {tmp[k ++ ] = q[j ++ ];count += mid - i + 1;}
else tmp[k ++ ] = q[i ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext())
{
int n = scan.nextInt();
if(n == 0) break;
for(int i = 0;i < n;i++) arr[i] = scan.nextLong();
merge_sort(arr,0,n - 1);
System.out.println(count);
count = 0;
}
}
}
为什么我的代码超时了?求解