python - 如何找到对列表进行排序的最少移动次数？

Question

在给定的 N 个不同整数的列表 A 中，我想通过将元素按升序移动到列表末尾来找到对列表进行排序所需的最小移动次数。

output is:1 4 3 2 5 [1, 3, 2, 5, 4] 1 [1, 2, 5, 4, 3] 2 [1, 2, 4, 3, 5] 3 [1, 2, 3, 5, 4] 4 [1, 2, 3, 4, 5] 5 None

def end_sort(a,c):
    for i in range(len(a)):
        if(a[i]>a[i+1]):
            a.append(a.pop(i))
            c+=1 
            print(a,c)
            break
    if(a!=sorted(a)):
        end_sort(a,c)
    else:
        return c 
a=list(map(int,input().split(" ")))
c=0
co=end_sort(a,c)
print(co,end="") 

Answer 1

让我们首先观察以下事实。

1. 求最小步数，一个数只能移动一次；
2. 必须先移动较小的数字才能在左边结束；
3. 如果右边的数字较小，则数字不合适。

考虑到这一点，我们可以从右到左遍历列表并跟踪非递减的数字 (3)。通过对这些数字 (2) 进行排序，我们得到了最佳步骤。这是最佳选择，因为必须移动的数字只移动一次 (1)。

def end_sort_steps(lst):
    steps = []
    right_min = max(lst)

    for n in reversed(lst):
        if n >= right_min:
            # Then the number must be moved
            steps.append(n)
        else:
            # Otherwise it is the smallest number seen yet
            right_min = n

    return sorted(steps)

print(end_sort_steps([1, 4, 3, 2, 5])) # [3, 4, 5]
# This corresponds to the steps:
# [1, 4, 3, 2, 5] -> [1, 4, 2, 5, 3] -> [1, 2, 5, 3, 4] -> [1, 2, 3, 4, 5]

根据您对该算法的用途，剩下的就是将该输出放入可用格式以表示您的步骤序列。

或者，如果这很重要，您可以简单地保留步数。

def end_sort_steps(lst):
    steps = 0
    right_min = max(lst)

    for n in reversed(lst):
        if n >= right_min:
            # Then the number must be moved
            steps += 1
        else:
            # Otherwise it is the smallest number seen yet
            right_min = n

    return steps