在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
以上是 在python中使用插入排序找出对数组进行排序所需的移位次数的程序 的全部内容， 来源链接： utcz.com/z/341284.html
