使用 Python 中的插入排序找出对数组进行排序所需的移位次数的程序

pythonserver side programmingprogramming更新于 2025/12/17 8:44:17

假设我们得到一个数组并被要求对其进行插入排序。在插入排序中，数组中的每个元素都会移位到数组中的正确位置。我们必须找出对数组进行排序所需的总移位次数。总移位次数是一个整数，如果数组已经排序，我们返回 0。

因此，如果输入类似于 input_array = [4, 5, 3, 1, 2]，则输出将为 8

[4, 5, 3, 1, 2] = 0 shifts

[4, 5, 3, 1, 2] = 0 shifts

[3, 4, 5, 1, 2] = 2 shifts

[1, 3, 4, 5, 2] = 3 shifts

[1, 2, 3, 4, 5] = 3 shifts

总移位次数为 = 0 + 0 + 2 + 3 + 3 = 8。

为了解决这个问题，我们将遵循以下步骤 −

length := input_arr 的大小
temp_arr := 一个大小为 1000001 的新列表，用 0 初始化
ans := 0
对于 input_arr 中的每个项目，执行
- val := item
- while val > 0，执行
  - ans := ans + temp_arr[val]
  - val := val - (val AND -val)
- val := item
- 当 val <= 1000000 时，执行
  - temp_arr[val] := temp_arr[val] + 1
  - val := val + (val AND -val)
ans := length * (floor value of (length - 1) / 2) - ans
返回 ans

示例

让我们看看下面的实现以便更好地理解 −

def solve(input_arr):
   length = len(input_arr)
   temp_arr = [0] * 1000001
   ans = 0
   for item in input_arr:
      val = item
      while val > 0:
         ans += temp_arr[val]
         val -= val & -val
      val = item
      while val <= 1000000:
         temp_arr[val] = temp_arr[val] + 1
         val += val & -val
   ans = length * (length - 1) // 2 - ans
   return ans

print(solve([4, 5, 3, 1, 2]))