将1~n乱序列表分为大小两半的最小相邻交换步数及函数修复

给定一个包含1到2n的乱序列表（n为偶数），每次仅能交换相邻元素，求将列表排序为左半部分全是1_{n的较小数、右半部分全是n+1}2n的较大数所需的最小步数。

现有如下Python函数：

def solve(t):
    count = 0
    n = len(t)//2
    for i in range(1,n+1):
        if t[-i] <= n:
            count += 1
    if t[0] == 1:
        n -= 1
    return count*n

该函数在部分用例中可正常返回结果：

• solve([2, 1, 4, 3])返回0（列表已符合要求）
• solve([5, 3, 4, 1, 6, 2])返回6（对应正确的6步排序过程）

但在测试用例solve([5, 2, 6, 4, 1, 3])时，函数返回6，而实际达到目标排序需要7步，说明该函数存在错误，需要修复。

问题分析 #

原有函数的核心错误在于：

1. 仅通过统计右半部分中小数的数量count，再用count*n计算步数，这是一种粗糙的近似，完全忽略了这些小数的实际位置以及它们之间的相对位置对总步数的影响。
2. 额外的t[0] == 1判断逻辑没有任何理论依据，属于冗余且错误的处理逻辑。

正确的思路应该聚焦于：所有1~n的小数最终需要占据列表的前n个位置，每个小数当前位置与目标位置的差值之和，就是所需的总相邻交换步数（因为相邻交换的步数等价于元素需要移动的距离，而小数之间的相对移动也会被自动计入总和）。

修复后的函数 #

def solve(t):
    n = len(t) // 2
    # 收集所有属于左半部分的小数的索引
    small_indices = []
    for idx, num in enumerate(t):
        if num <= n:
            small_indices.append(idx)
    # 计算总步数：每个小数需要移动到目标位置i（0到n-1），累加当前索引与目标索引的差值
    total_steps = 0
    for i in range(n):
        total_steps += small_indices[i] - i
    return total_steps

测试验证 #

• 用例[2, 1, 4, 3]：small_indices为[0,1]，总步数为(0-0)+(1-1)=0，正确。
• 用例[5, 3, 4, 1, 6, 2]：small_indices为[1,3,5]，总步数为(1-0)+(3-1)+(5-2)=6，正确。
• 用例[5, 2, 6, 4, 1, 3]：small_indices为[1,3,5]，总步数为(1-0)+(3-1)+(5-2)=7，与实际所需步数一致，正确。

内容的提问来源于stack exchange，提问作者user17438591