编辑代码

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;

            //数组长度小于2的时候不存在逆数对
            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;
        }
}