AcWing 788. 逆序对的数量

原题链接：https://www.acwing.com/problem/content/description/790/

首先根据定理：交换紧邻的一个逆序对会使得整个数组的逆序对数量减一，我们可以得知，冒泡排序中元素交换的次数即等于逆序对的个数。

所以，可以直接使用冒泡排序统计逆序对的数量：

void bubble_sort(int nums[], int left, int right) {
    for (int i = 0; i < right - left; i++) {
        for (int j = left; j < right - i - 1; j++) {
            if (nums[j] > nums[j+1]) {
                swap(nums[j], nums[j+1]);
                count++;
            }
        }
    }
}

但是冒泡排序的复杂度是，效率太低。

我们可以考虑采用分治思想，将数组一分为二，然后求出：

• 左半部分逆序对的个数
• 右半部分逆序对的个数
• 跨越分界点的逆序对的个数

最后将三者相加即得答案。不难发现，我们可以将其与归并排序算法结合起来。

#define LL long long

LL merge_sort(int nums[], int left, int right) {
    if (right - left <= 1) return 0;
    
    int mid = (left + right) >> 1;
    
    LL left_count = merge_sort(nums, left, mid);
    LL right_count = merge_sort(nums, mid, right);
    LL count = 0;
    
    int i = left, j = mid, k = 0;
    
    while (i < mid && j < right) {
        if (nums[i] > nums[j]) {
            count += (LL) (mid - i);
            tmp[k++] = nums[j++];
        }
        else { 
            tmp[k++] = nums[i++];
            
        }
    }
    
    while(i < mid) tmp[k++] = nums[i++];
    while(j < right) tmp[k++] = nums[j++];
    
    for (int i = left, j = 0; i < right; ++i, ++j) nums[i] = tmp[j];
    
    return left_count + right_count + count;
}

其中的不同之处在于，将已经有序的两部分数组合并到临时数组时，我们统计跨越分界点的逆序对的个数。这样，算法的复杂度可以稳定在。