algorithm - 有效地排序排列

Question

给定 [n] 的未排序排列，我想通过从左到右迭代来收集数字，以便对预排列 (1...n) 进行排序。
为了实现这个目标，我必须进行多少次迭代？
例如:
给定 '3, 7, 4, 2, 10, 8, 9, 1, 6, 5' - 迭代次数为 6。
在第一次迭代中，我将收集数字 1
在第二次迭代中，我将收集数字 2
在第三次迭代中，我将收集数字 3、4、5
在第四次迭代中，我将收集数字 6
在第五次迭代中，我将收集数字 7、8、9
在第六次迭代中，我将收集数字 10

我构建了一个天真的代码，用 O(n^2) 完成任务，但我需要它更高效，所以我认为我在这里缺少一个技巧。
有什么建议吗？

Answer 1

反转排列，然后计算两个连续数字递减加一的次数。

def iterations(perm):
    invperm = [None] * len(perm)
    for i in range(len(perm)):  # yes, we could use enumerate
        invperm[perm[i] - 1] = i
    count = 1
    for i in range(1, len(perm)):
        count += invperm[i - 1] > invperm[i]
    return count

解释:

     Given          : 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

                 x  : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Index of x in the given array : |8, |4, |1, 3, 10, |9, |2, 6, 7, |5

如果索引乱序，则必须重新开始。因此，如果您计算 |，那么您就知道需要的迭代次数。