标签：sort 归并 python arr print inversions 序数
def merge_sort_and_count_inversions(arr):
n = len(arr)
if n <= 1:
return arr, 0 # 如果n小于等于1，数组已经有序，直接返回数组本身和逆序数0
mid = n // 2
left_lst, inv_left = merge_sort_and_count_inversions(arr[:mid]) # 对左半部分进行递归，并获取结果和逆序数
right_lst, inv_right = merge_sort_and_count_inversions(arr[mid:]) # 对右半部分进行递归，并获取结果和逆序数
# 分解完，该合并了
left_pointer, right_pointer = 0, 0 # 两个指针
result = [] # 定义一个空列表进行存储数据
inv_merge = 0 # 用于记录合并时产生的逆序数
while left_pointer < len(left_lst) and right_pointer < len(right_lst): # 当两个指针没有超出各自的范围时
if left_lst[left_pointer] <= right_lst[right_pointer]:
result.append(left_lst[left_pointer])
left_pointer += 1
else:
result.append(right_lst[right_pointer])
right_pointer += 1
# 每当一个右半部分的元素被加入结果列表时，说明它和左半部分剩下的所有元素都构成了逆序对
inv_merge += len(left_lst) - left_pointer
# 当退出循环后，将剩余的部分添加到result中
result += left_lst[left_pointer:]
result += right_lst[right_pointer:]
# 返回合并后的结果和总的逆序数
return result, inv_left + inv_right + inv_merge
# 示例数组
arr = [1, 5, 3, 4, 2, 6]
# 计算排序后的数组和逆序数
sorted_arr, inversions = merge_sort_and_count_inversions(arr)
print(f"原数组是: {sorted_arr}")
print(f"逆序数个数是: {inversions}")
标签：sort,
归并,
python,
arr,
print,
inversions,
序数
From： https://blog.csdn.net/qingcheng_123456/article/details/137357006