每日算法 — 使用java实现逆序对：归并排序分治与树状数组优化

逆序对是算法面试与竞赛中的经典问题，它衡量了一个序列的”有序程度”。本文深入讲解逆序对的两种高效解法——归并排序分治法和树状数组法，并给出完整的Java实现。

什么是逆序对

在一个序列中，如果存在一对元素满足 i < j 但 nums[i] > nums[j]，则称 (i, j) 为一个逆序对。

示例：序列 [3, 1, 4, 2] 中的逆序对有：
– (3, 1)：3 > 1 且索引 0 < 1
– (3, 2)：3 > 2 且索引 0 < 3
– (4, 2)：4 > 2 且索引 2 < 3

总共有 3 个逆序对。逆序对数量越多，说明序列越”混乱”。

解法一：归并排序分治法

核心思想

归并排序在合并两个有序子数组时，可以顺便统计跨子数组的逆序对：
– 左子数组 left 和右子数组 right 已经分别有序
– 当 left[i] > right[j] 时，由于左子数组有序，left[i] 及其之后的所有元素都大于 right[j]
– 因此逆序对增加 (mid - i + 1) 个

时间复杂度：O(n log n)，空间复杂度：O(n)

Java实现

/**
 * 逆序对计数：归并排序分治法
 * 利用归并排序的合并过程，在 O(n log n) 时间内统计逆序对
 */
public class InversionCountMergeSort {

    private long inversionCount = 0;

    /**
     * 统计数组中的逆序对数量
     * @param nums 输入数组
     * @return 逆序对总数
     */
    public long countInversions(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        inversionCount = 0;
        int[] temp = new int[nums.length];
        mergeSort(nums, temp, 0, nums.length - 1);
        return inversionCount;
    }

    /**
     * 归并排序并统计逆序对
     */
    private void mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;

        // 分治：分别统计左右子数组的逆序对
        mergeSort(nums, temp, left, mid);
        mergeSort(nums, temp, mid + 1, right);

        // 合并：统计跨左右子数组的逆序对
        merge(nums, temp, left, mid, right);
    }

    /**
     * 合并两个有序子数组，并统计跨子数组的逆序对
     */
    private void merge(int[] nums, int[] temp, int left, int mid, int right) {
        // 复制到临时数组
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;      // 左子数组指针
        int j = mid + 1;   // 右子数组指针
        int k = left;      // 合并后数组的写入位置

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                // 无逆序对，直接放入
                nums[k++] = temp[i++];
            } else {
                // 发现逆序对：temp[i] > temp[j]
                // 由于左子数组有序，temp[i..mid] 都大于 temp[j]
                nums[k++] = temp[j++];
                inversionCount += (mid - i + 1);
            }
        }

        // 处理剩余元素
        while (i <= mid) {
            nums[k++] = temp[i++];
        }
        while (j <= right) {
            nums[k++] = temp[j++];
        }
    }

    /**
     * 扩展：找出所有逆序对的具体位置（仅用于小规模数据演示）
     */
    public void printAllInversions(int[] nums) {
        System.out.println("所有逆序对:");
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    System.out.printf("  (%d, %d): nums[%d]=%d > nums[%d]=%d%n", 
                        i, j, i, nums[i], j, nums[j]);
                    count++;
                }
            }
        }
        System.out.println("总数量: " + count);
    }

    public static void main(String[] args) {
        InversionCountMergeSort solver = new InversionCountMergeSort();

        int[] nums1 = {3, 1, 4, 2};
        System.out.println("=== 归并排序法统计逆序对 ===");
        System.out.println("原始数组: " + java.util.Arrays.toString(nums1));
        System.out.println("逆序对数量: " + solver.countInversions(nums1.clone()));
        solver.printAllInversions(nums1);

        // 大规模测试
        int[] nums2 = {7, 5, 6, 4, 3, 8, 2, 1};
        System.out.println("\\n原始数组: " + java.util.Arrays.toString(nums2));
        System.out.println("逆序对数量: " + solver.countInversions(nums2.clone()));
    }
}

解法二：树状数组（Fenwick Tree）法

核心思想

树状数组适合处理动态前缀和查询问题。逆序对计数的思路：
1. 离散化：将数值映射到排名（1 ~ n），避免大数值问题
2. 从右向左扫描：对于每个元素 nums[i]，查询已经处理过的元素中有多少个小于它的
3. 树状数组维护频率：在对应排名位置 +1，并查询前缀和

时间复杂度：O(n log n)，空间复杂度：O(n)

Java实现

import java.util.*;

/**
 * 逆序对计数：树状数组法
 * 通过离散化 + 树状数组维护频率，从右向左扫描统计
 */
public class InversionCountFenwick {

    /**
     * 树状数组（Fenwick Tree / Binary Indexed Tree）
     */
    static class FenwickTree {
        int[] tree;
        int n;

        FenwickTree(int n) {
            this.n = n;
            this.tree = new int[n + 1]; // 1-based indexing
        }

        /**
         * 在位置 idx 增加值 val
         */
        void update(int idx, int val) {
            while (idx <= n) {
                tree[idx] += val;
                idx += idx & -idx;  // 加上 lowbit，移动到父节点
            }
        }

        /**
         * 查询前缀和 [1, idx]
         */
        int query(int idx) {
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;  // 减去 lowbit，移动到前一个区间
            }
            return sum;
        }
    }

    /**
     * 离散化：将原始数值映射到 1 ~ n 的排名
     */
    private int[] discretize(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        // 去重（使用 TreeSet 或直接遍历）
        int uniqueCount = 1;
        for (int i = 1; i < n; i++) {
            if (sorted[i] != sorted[i - 1]) {
                sorted[uniqueCount++] = sorted[i];
            }
        }

        int[] ranks = new int[n];
        for (int i = 0; i < n; i++) {
            ranks[i] = Arrays.binarySearch(sorted, 0, uniqueCount, nums[i]) + 1;
        }
        return ranks;
    }

    /**
     * 统计逆序对数量
     */
    public long countInversions(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }

        int n = nums.length;
        int[] ranks = discretize(nums);
        FenwickTree ft = new FenwickTree(n);
        long inversions = 0;

        // 从右向左扫描
        for (int i = n - 1; i >= 0; i--) {
            // 查询当前排名之前有多少个数已经被记录（即右侧比当前数小的数的个数）
            inversions += ft.query(ranks[i] - 1);
            // 将当前数的排名加入树状数组
            ft.update(ranks[i], 1);
        }

        return inversions;
    }

    /**
     * 扩展：计算每个元素作为逆序对左端点的个数
     */
    public int[] countLeftInversions(int[] nums) {
        int n = nums.length;
        int[] ranks = discretize(nums);
        FenwickTree ft = new FenwickTree(n);
        int[] leftCount = new int[n];

        // 从左向右扫描：统计每个元素左侧比它大的数的个数
        for (int i = 0; i < n; i++) {
            // 总数 - 前缀和 = 左侧比当前数大的数的个数
            leftCount[i] = i - ft.query(ranks[i]);
            ft.update(ranks[i], 1);
        }

        return leftCount;
    }

    public static void main(String[] args) {
        InversionCountFenwick solver = new InversionCountFenwick();

        int[] nums = {3, 1, 4, 2, 5, 7, 6};
        System.out.println("=== 树状数组法统计逆序对 ===");
        System.out.println("原始数组: " + Arrays.toString(nums));
        System.out.println("逆序对数量: " + solver.countInversions(nums.clone()));

        System.out.println("\\n每个元素作为左端点的逆序对个数:");
        int[] leftCounts = solver.countLeftInversions(nums.clone());
        for (int i = 0; i < nums.length; i++) {
            System.out.printf("  nums[%d]=%d: %d 个%n", i, nums[i], leftCounts[i]);
        }
    }
}

两种方法对比

实际应用场景

1. 衡量序列混乱程度：逆序对数量与冒泡排序交换次数相等
2. 相似度计算：在推荐系统中，通过逆序对数量衡量两个排序列表的差异
3. Kendall Tau距离：基于逆序对的排序相关性度量
4. 数据流处理：树状数组法可以动态维护逆序对数量

掌握逆序对的两种解法，可以帮助你更深入地理解分治与树状数组这两个核心算法思想。