使用Python插入排序查找数组所需的移位次数

使用Python插入排序查找数组所需的移位次数

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

所以,如果输入如下input_array = [4, 5, 3, 1, 2],则输出为8。

[4, 5, 3, 1, 2] = 0 移位次数

[4, 5, 3, 1, 2] = 0 移位次数 

[3, 4, 5, 1, 2] = 2 移位次数

[1, 3, 4, 5, 2] = 3 移位次数

[1, 2, 3, 4, 5] = 3 移位次数 

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

为了解决这个问题,我们将按照以下步骤进行−

  • length :=输入数组的大小
  • temp_arr :=大小为1000001的新列表,初始化为0
  • ans := 0
  • 对于输入数组中的每个项,执行以下操作
    • val := 项
    • while val > 0,执行
      • ans := ans + temp_arr[val]
      • val := val – (val AND -val)
    • val := 项
    • while val <= 1000000,执行
      • temp_arr[val] := temp_arr[val] + 1
      • val := val + (val AND -val)
  • ans := length * (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]))

输入

[4, 5, 3, 1, 2]

输出

8

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程