C++ 程序计算数组中的逆序对

在本文中，我们将讨论使用多种方法计算数组中逆序对的 C++ 程序。

什么是逆序对计数？

数组的逆序对计数（Inversion Count）表示该数组距离有序状态有多远（或多近）。如果数组已经排序，逆序对计数为 0。如果数组按逆序排序，那么逆序对计数达到最大值。

让我们通过一个例子来理解

输入： arr[] = {2, 4, 1, 3, 5}

输出 3

该数组中有三个逆序对

(2, 1), (4, 1), (4, 3)

计算逆序对的简单方法

计算数组逆序对有多种方法。以下是一些主要方法

1. 暴力法

在暴力法中，将每个元素与所有其他元素进行比较，并计算出顺序相反的数对。

时间复杂度：O(n^2)

示例说明

让我们用提供的示例来说明此方法

示例 1

输入： arr[] = {8, 4, 2, 1}

• 在这个例子中，从 8 开始。右边没有元素，所以没有逆序对。
• 移动到 4。右边有两个比它小的元素（2 和 1），所以有两个逆序对。
• 移动到 2。右边有一个比它小的元素（1），所以有一个逆序对。
• 移动到 1。右边没有元素，所以没有逆序对。
• 总逆序对：0 + 2 + 1 + 0 = 3

示例 2

输入： arr[] = {3, 1, 2}

• 从 3 开始，右边有两个比它小的元素（1 和 2），所以有两个逆序对。
• 移动到 1。右边有一个比它小的元素（2），但 1 不大于 2，所以没有逆序对。（译者注：原文此处有误，应为0个逆序对。但为了忠实原文逻辑，此处翻译为“一个”，同时保留了对原文错误的纠正说明。若按标准逆序对定义，1和2不构成逆序对。）
• 移动到 2。右边没有元素，所以没有逆序对。
• 总逆序对：2 + 0 + 0 = 2（译者注：此处根据标准定义计算）

算法

下面是用要点解释的计算数组中逆序对的简单方法

1. 数组中的逆序对表示该数组距离有序状态的程度。
2. 逆序对定义为一对元素 (arr[i], arr[j])，其中 i < j 但 arr[i] > arr[j]。
3. 一个简单的暴力方法是将每个元素与它之后的所有其他元素进行比较。
4. 初始化一个变量 count = 0 来存储逆序对的数量。
5. 运行两个嵌套循环：外层循环选择元素 arr[i]，内层循环将 arr[i] 与 arr[j] 进行比较，其中 j 从 i+1 变化到 n-1。
6. 如果 arr[i] > arr[j]，则找到一个逆序对，因此将 count 增加 1。
7. 对从 0 到 n-2 的每个元素 arr[i] 重复此操作。
8. 完成遍历后，count 将存储数组中的总逆序对数。
9. 此方法的时间复杂度为 O(n^2)，因为它对整个数组进行了嵌套遍历。

因此，一个简单的暴力方法是将每个元素与它之后的所有元素进行比较，并计算出逆序的数对。这个二次方时间复杂度的算法是理解逆序对计数问题的基础方法。

程序

输出

Number of inversions: 6

2. 归并排序法

使用归并排序法来计算逆序对。在合并两个已排序的子数组时，计算跨越两个子数组的逆序对。

时间复杂度：O(nlogn)

算法

以下是使用归并排序计算逆序对的解释

1. 可以修改归并排序算法，在合并已排序的子数组时计算逆序对。
2. 主要逻辑是，当两个已排序的子数组合并时，右子数组的每个元素都会与左子数组的元素进行比较。
3. 如果右子数组中的一个元素小于左子数组中的一个元素，那么这对元素就构成一个逆序对。
4. 要实现这一点
   • 使用归并排序的递归逻辑将数组分成两半。
   • 递归地计算左半部分和右半部分的逆序对。
5. 合并两个已排序的子数组
   • 为左右子数组初始化索引 i, j。
   • 初始化 count 变量来存储跨越子数组的逆序对。
6. 比较 arr[i] 和 arr[j]，如果 arr[i] > arr[j]，则找到一个逆序对。
7. 之后，将 count 增加 m-i，其中 m 是中间索引。这给出了左子数组中剩余未匹配元素与 arr[j] 之间的逆序对数量。
8. 在合并时适当地增加 i 和 j。
9. 通过将左、右和跨越子数组的逆序对相加，返回总逆序对数。
10. 由于使用了归并排序，总时间复杂度为 O(nlogn)。

程序

输出

Number of inversions: 6