在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。
示例
让我们看看以下实现以获得更好的理解-
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-答案
return ans
print(solve([4, 5, 3, 1, 2]))输入
[4, 5, 3, 1, 2]输出结果
8