归并排序求逆序对的代码

<think>嗯，用户让我介绍一下归并排序求逆序对的代码。首先，我需要回忆一下归并排序的基本原理，以及逆序对的定义。归并排序是分治算法，把数组分成两半，分别排序后再合并。而逆序对指的是数组中前面的元素大于后面的元素的情况。例如，在数组[3,1,2]中，逆序对有(3,1)和(3,2)，所以总共有2个。 那归并排序过程中如何计算逆序对呢？在合并两个已排序的子数组时，如果左边的元素大于右边的元素，那么左边该元素及其后面的元素都会与右边的这个元素构成逆序对。例如，合并时左边是[3,4]，右边是[1,2]，当比较3和1时，3>1，所以逆序对的数量应该是左边剩余元素的数量（这里左边此时有2个元素），所以逆序对增加2。这一步是关键，需要正确统计这个数量。 接下来，我需要考虑如何修改归并排序的代码来统计逆序对的数量。通常归并排序的合并过程需要临时数组，然后在合并时进行比较。这时候，当右边的元素被选中放入临时数组时，说明左边的当前元素比右边的大，这时候逆序对的数量需要加上左边剩余元素的个数，也就是mid - i + 1，其中i是左边子数组的当前指针，mid是左边子数组的末尾。 可能的代码结构应该是这样的：主函数调用一个递归函数，该函数返回逆序对的数量。递归函数先分割数组到单个元素，然后合并并统计逆序对的数量。合并过程中，每次从左右子数组中取较小的元素，当取右子数组的元素时，累加逆序对的数量。 需要注意的点包括：数组的索引是否正确，例如mid的计算，以及临时数组的处理。另外，逆序对的累加应该在合并过程中正确计算。例如，当左边元素大于右边元素时，逆序对的数量增加左边剩余元素的数目。 举个例子，比如数组是[5,3,2,4,1]。用归并排序分割到最小单位后，合并时计算逆序对。比如在合并[5]和[3]的时候，5>3，所以逆序对加1。合并后的数组是[3,5]，然后再合并更大的部分，每一步都要统计这些情况。 可能还要考虑大数情况下的性能，因为如果数组很大，递归可能导致栈溢出，但通常归并排序在处理大规模数据时还是可以的，因为时间复杂度是O(n log n)，而逆序对的计算不会增加复杂度，只是常数时间上的增加。 另外，边界条件需要注意，比如数组长度为0或1时，逆序对数量为0。测试用例方面，可以测试已知的情况，比如数组倒序排列时逆序对数量最大，为n(n-1)/2。例如，数组[4,3,2,1]的逆序对数是6。 在代码实现时，可能需要注意数组的索引是否正确，比如在分割时左半部分是left到mid，右半部分是mid+1到right。合并过程中，i指向左半部分的起始，j指向右半部分的起始，当nums[i] > nums[j]时，逆序对数目加上mid - i + 1。因为此时左半部分从i到mid的所有元素都会比nums[j]大，所以贡献mid - i +1个逆序对。 所以，总结下来，归并排序求逆序对的代码结构大致如下： 定义一个全局或传递的计数器，或者在递归过程中返回逆序对数目。合并函数返回本次合并中的逆序对数目，然后递归地将左右子数组的数目相加，再加上合并过程中的数目。 具体的代码实现可能需要使用辅助数组来存放合并后的结果，同时在合并过程中统计逆序对的数量。递归函数的结构可能类似： def merge_sort(nums, left, right): if left >= right: return 0 mid = (left + right) // 2 count = merge_sort(nums, left, mid) + merge_sort(nums, mid+1, right) count += merge(nums, left, mid, right) return count 其中merge函数负责合并并返回该次合并中的逆序对数目。merge函数中，当左半部分的元素大于右半部分时，累加mid - i + 1到count中。 编写merge函数时，需要创建临时数组，然后比较左右两部分的元素，按顺序放入临时数组，同时统计逆序对的数量。例如： def merge(nums, left, mid, right): temp = [] i = left j = mid + 1 count = 0 while i <= mid and j <= right: if nums[i] <= nums[j]: temp.append(nums[i]) i += 1 else: temp.append(nums[j]) count += mid - i + 1 j += 1 # 处理剩余元素 temp.extend(nums[i:mid+1]) temp.extend(nums[j:right+1]) # 将临时数组复制回原数组 nums[left:right+1] = temp return count 这样，在每次合并的时候，当右半部分的元素被选中时，累加对应的逆序对数目。整个归并排序完成后，累计的count就是总的逆序对数目。 需要注意的地方是原数组会被修改，所以如果需要保留原数组，可能需要先复制一份。例如，在调用的时候，可以复制数组，然后对复制的数组进行排序和计算。 例如，主函数可能是： def count_inversions(nums): # 复制原数组，避免修改原数组 temp_nums = nums.copy() return merge_sort(temp_nums, 0, len(temp_nums)-1) 测试的时候，比如输入[3,1,2]，应该返回2。输入[1,2,3,4]返回0，输入[4,3,2,1]返回6。 可能的错误点包括： 1. 索引计算错误，比如mid的计算是否正确，是否导致分割错误。 2. 在合并时，i的范围是left到mid，j是mid+1到right，所以在处理剩余元素的时候，应该用nums[i:mid+1]，而不是到mid，因为切片是左闭右开的，所以mid+1作为结束索引可以包含到mid的元素。 3. 修改原数组的部分是否正确，即nums[left:right+1] = temp，因为right是包含的，所以切片结束是right+1。 另外，关于空间复杂度，归并排序需要O(n)的额外空间，这在处理大数组时可能需要注意。 现在，综合这些思考，可以编写出正确的归并排序求逆序对的代码。</think>以下是使用归并排序计算逆序对的中文代码实现及详细解释： ### 代码实现 ```python def count_inversions(nums): def merge_sort(arr, left, right): if left >= right: return 0 mid = (left + right) // 2 # 分治递归计算左右子数组的逆序对 count = merge_sort(arr, left, mid) + merge_sort(arr, mid+1, right) # 合并过程并统计逆序对 count += merge(arr, left, mid, right) return count def merge(arr, left, mid, right): temp = [] # 临时合并数组 i, j = left, mid+1 count = 0 # 当前合并步骤的逆序对计数 # 左右子数组均未遍历完时比较 while i <= mid and j <= right: if arr[i] <= arr[j]: temp.append(arr[i]) i += 1 else: temp.append(arr[j]) # 关键统计逻辑：左半数组剩余元素都与arr[j]构成逆序对 count += mid - i + 1 j += 1 # 处理剩余元素 temp.extend(arr[i:mid+1]) # 左半剩余 temp.extend(arr[j:right+1]) # 右半剩余 # 将合并结果写回原数组 arr[left:right+1] = temp return count # 创建副本避免修改原数组 return merge_sort(nums.copy(), 0, len(nums)-1) # 测试示例 print(count_inversions([3, 1, 2])) # 输出: 2 print(count_inversions([5, 3, 2, 4, 1])) # 输出: 7 print(count_inversions([4, 3, 2, 1])) # 输出: 6 ``` --- ### 核心原理 1. **分治策略** - 将数组递归拆分为左右两半，分别计算各自的逆序对数量。 - 合并时统计跨越左右子数组的逆序对。 2. **关键合并逻辑** - 当右子数组元素被放入临时数组时，左子数组剩余的所有元素均与该元素构成逆序对。 - 计算公式：`逆序对增量 = mid - 当前左指针 + 1` --- ### 复杂度分析 - **时间复杂度**：O(n log n) 与归并排序相同，合并过程总计执行 log n 层，每层处理 n 个元素。 - **空间复杂度**：O(n) 临时数组存储合并结果。 --- ### 关键点说明 - **原数组保护**：通过`nums.copy()`避免修改输入数据。 - **索引计算**：`mid`值为`(left + right)//2`确保分割正确。 - **剩余元素处理**：使用`extend()`直接添加未遍历完的子数组。 此算法高效且优雅地利用归并排序的特性，在排序过程中同步完成逆序对统计。