数组中的逆序对 py charm
时间: 2024-02-01 19:02:56 浏览: 23
可以使用归并排序来解决数组中逆序对的问题。具体做法是在归并排序的过程中统计逆序对的个数。
以下是 Python 代码实现:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left_arr, left_count = merge_sort(arr[:mid])
right_arr, right_count = merge_sort(arr[mid:])
merged_arr, merge_count = merge(left_arr, right_arr)
return merged_arr, left_count + right_count + merge_count
def merge(left_arr, right_arr):
merged_arr = []
count = 0
i, j = 0, 0
while i < len(left_arr) and j < len(right_arr):
if left_arr[i] <= right_arr[j]:
merged_arr.append(left_arr[i])
i += 1
else:
merged_arr.append(right_arr[j])
j += 1
count += len(left_arr) - i
merged_arr += left_arr[i:]
merged_arr += right_arr[j:]
return merged_arr, count
if __name__ == '__main__':
arr = [3, 1, 4, 2, 5]
_, count = merge_sort(arr)
print(count) # 输出 4,因为逆序对有 (3, 1), (4, 2), (4, 1), (5, 2)
```
在归并排序的过程中,我们统计了左半部分和右半部分的逆序对个数,然后在合并两个有序数组的过程中统计跨越两个部分的逆序对个数。最终返回的是排好序的数组和逆序对个数。