如何快速计算0到N-1数组冒泡排序的交换次数？

首先明确：冒泡排序的交换次数等于数组的逆序数——也就是数组中满足i < j且arr[i] > arr[j]的数对总数。你现有的O(N²)代码本质是暴力统计逆序数，我们可以用O(N logN)的算法优化这个统计过程。

下面是两种高效的实现方案：

方案一：归并排序分治法 #

利用归并排序的分治过程，在合并左右两个有序子数组时，统计跨左右子数组的逆序数。当左子数组当前元素大于右子数组当前元素时，左子数组中当前位置及之后的所有元素都与右子数组当前元素构成逆序对，直接累加这个数量即可。

C++ 实现代码 #

long long countSwaps(vector<int>& arr) {
    vector<int> temp(arr.size());
    return mergeSort(arr, temp, 0, arr.size() - 1);
}

long long mergeSort(vector<int>& arr, vector<int>& temp, int left, int right) {
    long long count = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        count += mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid + 1, right);
        count += merge(arr, temp, left, mid, right);
    }
    return count;
}

long long merge(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    long long count = 0;
    int i = left;    // 左子数组指针
    int j = mid + 1; // 右子数组指针
    int k = left;    // 临时数组指针

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // 左子数组当前元素 > 右子数组当前元素，左子数组剩余元素都与arr[j]构成逆序对
            count += mid - i + 1;
            temp[k++] = arr[j++];
        }
    }

    // 拷贝剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // 将临时数组内容拷贝回原数组
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return count;
}

方案二：树状数组（Fenwick Tree）法 #

由于数组元素是0到N-1的连续整数，无需离散化处理。我们可以从后往前遍历数组，用树状数组维护已遍历元素的出现次数，对于每个元素x，查询树状数组中小于x的元素总数——这就是当前元素右侧比它小的元素个数（即与当前元素构成的逆序对数量），累加所有结果即可得到总逆序数。

C++ 实现代码 #

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 1, 0) {}

    void update(int idx, int delta) {
        idx++; // 因为元素可能为0，树状数组通常从1开始索引
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        idx++; // 对应update的偏移
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
};

long long countSwaps(vector<int>& arr) {
    int n = arr.size();
    FenwickTree ft(n);
    long long count = 0;
    // 从后往前遍历
    for (int i = n - 1; i >= 0; i--) {
        int x = arr[i];
        // 查询已加入的元素中小于x的数量
        count += ft.query(x - 1);
        // 将当前元素加入树状数组
        ft.update(x, 1);
    }
    return count;
}

复杂度说明 #

两种方案的时间复杂度均为O(N logN)，空间复杂度归并排序为O(N)，树状数组为O(N)，相比原O(N²)的实现，在N较大时（如N=1e5）性能提升极其明显。

内容的提问来源于stack exchange，提问作者Xyon4