Python程序：使用插入排序查找排序数组所需的交换次数

假设我们得到一个数组，并被要求对其执行插入排序。在插入排序中，数组中的每个元素都被移到其在数组中的正确位置。我们必须找出排序数组所需的总交换次数。总交换次数是一个整数，如果数组已经排序，则返回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
    • 当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 * (length - 1 的向下取整) - 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]))

输入

[4, 5, 3, 1, 2]

输出

8

更新于： 2021年10月9日

1K+ 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告