本文共 1494 字，大约阅读时间需要 4 分钟。

为了计算给定排列的逆序数，我们可以使用分治法结合归并排序的方法。这种方法的时间复杂度是O(n log n)，非常适合处理较大的n值（如n ≤ 100000）。

分治法的步骤

双指针法计算跨半逆序对

假设左半和右半已经排好序，使用双指针从两端开始比较：

• 左指针指向左半的开头，右指针指向右半的开头。
• 比较左右指针所指的元素：
  • 如果左半的元素小于右半的元素，左指针前进。
  • 否则，右指针前进，并增加逆序对的数量。

这种方法确保了每个元素只被访问一次，时间复杂度为O(n)。

代码实现

#include 
   
    
#include 
    
     
using namespace std;
long long sum = 0;
void mergeSort(int* arr, int s, int e, int* temp) {
    if (s >= e) return;
    int mid = s + (e - s) / 2;
    mergeSort(arr, s, mid, temp);
    mergeSort(arr, mid + 1, e, temp);
    mergeAndCount(arr, s, mid, e, temp);
}
void mergeAndCount(int* arr, int s, int mid, int e, int* temp) {
    int p1 = s, p2 = mid + 1;
    while (p1 <= mid && p2 <= e) {
        if (arr[p1] < arr[p2]) {
            temp[index++] = arr[p1++];
        } else {
            sum += mid - p1 + 1;
            temp[index++] = arr[p2++];
        }
    }
    while (p1 <= mid) {
        temp[index++] = arr[p1++];
    }
    while (p2 <= e) {
        temp[index++] = arr[p2++];
    }
}
int main() {
    int n;
    vector
     
       a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int* temp = new int[n];
    mergeSort(a.data(), 0, n-1, temp);
    cout << sum << endl;
    delete[] temp;
    return 0;
}
     
    
   

代码解释

这种方法不仅高效，还通过递归和迭代的结合，确保了代码的简洁和可维护性。