数列的逆序数对（难度系数：2颗星）

悠悠 2022-06-16 09:27 71阅读 0赞

给定一个数列，求数列的逆序数对总个数（逆序数对就是指数列中的两个数，排在前面的数比排在后面的数大，这样就构成了一个逆序数对）。

例如： 4 2 1 3

这个数列的逆序数对有： (4, 2);(4, 1);(4, 3);(2, 1);总共有4个逆序数对。

PS：其实完全是使用了归并排序的思想，只是在合并的时候多加了一句统计该范围内的逆序数的个数，我们累加每一个小区间的逆序数个数，自然就得到了整个数列的逆序数对总个数。

参考代码：

#include<stdio.h>
    
    int arr[] = { 5, 15, 99, 45, 12, 1, 90, 19, 33, 41 };
    int tmp[100];
    int nInverseCount = 0;//保存逆序数对个数
    
    void Merge(int s, int m, int t)
    {
        int i = s, j = m + 1, k = s;
        while (i <= m && j <= t)
        {
            if (arr[i] <= arr[j])
                tmp[k++] = arr[i++];
            else
            {
                tmp[k++] = arr[j++];
                nInverseCount += j - k;//这句话也可以写成nInverseCount += m - i + 1;本质都是用来统计由arr[j]导致的逆序数对个数
            }
        }
        while (i <= m)
            tmp[k++] = arr[i++];
        while (j <= t)
            tmp[k++] = arr[j++];
    }
    
    void MergeSoft(int s, int t)
    {
        int i, m;
        if (s < t)
        {
            m = (s + t) / 2;
            MergeSoft(s, m);
            MergeSoft(m + 1, t);
            Merge(s, m, t);
            for (i = s; i <= t; i++)
                arr[i] = tmp[i];
        }
    }
    
    int main()
    {
        int i, nCount = sizeof(arr) / sizeof(arr[0]);
        printf("排序前\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
    
        MergeSoft(0, nCount - 1);
    
        printf("\n排序后\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
    
        printf("\n逆序数对个数为: %d\n", nInverseCount);
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/2a9c820202ef4cfb9b1190b9e72af2f2.png