using System;
public class HelloWorld
{
public static void Main()
{
int[] arr = new int[] { 2, 4, 3, 1, 5, 6 };
var result = ReversePairs(arr);
Console.WriteLine($"逆序对个数:{result}");
}
public static int ReversePairs(int[] nums)
{
int len = nums.Length;
if (len < 2) return 0;
int[] temp = new int[len];
return ReversePairs(nums, 0, len - 1, temp);
}
private static int ReversePairs(int[] nums, int left, int right, int[] temp)
{
if (left == right) return 0;
int mid = left + (right - left) / 2;
int leftPairs = ReversePairs(nums, left, mid, temp);
int rightPairs = ReversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1])
return leftPairs + rightPairs;
int crossPairs = MergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
private static int MergeAndCount(int[] nums, int left, int mid, int right, int[] temp)
{
for (int k = left; k <= right; k++)
{
temp[k] = nums[k];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++)
{
if (i == mid + 1)
{
nums[k] = temp[j];
j++;
}
else if (j == right + 1)
{
nums[k] = temp[i];
i++;
}
else if (temp[i] <= temp[j])
{
nums[k] = temp[i];
i++;
}
else
{
nums[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
}