问高效排序排列

EN

颠倒排列，然后计算两个连续数字递减的次数，加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

解释：

给定数组中x的

Given : 3, 7, 4, 2, 10, 8, 9, 1, 6, 5 x : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 索引：|8，|4，|1，3，10，|9，|2，6，7，|5

如果索引顺序不正确，那么您必须重新开始。因此，如果你计算|s，那么你就知道你需要的迭代次数。

如果你知道，假设给定了一个数组，其中肯定存在n的排列的所有元素，那么我认为：

分配一个数组和一个循环从循环到循环搜索未排序元素的初始数组x在每次迭代中收集项的方式如下：y[x[i]] := x[i]

• After

1. 1 in n x is a sorted iteration with O (n)

欧洲中部时间--编辑时间20-12-2014 22:54 ：

上面的解决方案只适用于这样的情况，其中存在n-elementh表，该表包含以任何给定方式从1到n的无序整数。

我将根据您的示例详细解释如何通过输入数组进行一次迭代即可实现此目标。

让我们以初始数组为例：

x[] = { 3, 7, 4, 2, 10, 8, 9, 1, 6, 5 }

因此，让我们使用以下从零开始填充的数组：

y[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

现在让下面的有序列表中的每一项都是排序算法的迭代：

我们取等于3的x[1] -让我们把它写在结果表yy[3] := 3的第3位(实际上是：y[x[1]] := x[1])，结果表现在看起来如下所示

y[] ={ 0，0，3，0，0，0，0，0，0，0}

• 在第二步中，我们获取等于7的x[2]，并重复这些步骤：

y[7] := 7 (实际上是：y[x[2]] := x[2])

结果表现在如下所示

y[] ={ 0，0，3，0，0，0，0，7，0，0，0}

• 第三步：x[3]等于4y[4] := 4 (实际为：y[x[3]] := x[3])结果表：

y[] ={ 0，0，3，4，0，0，7，0，0，0 y[]={0，0，3，4，0，0，7，0，0 2y[2] := 2 (实际为：y[x[4]] := x[4])结果表：

}

• x[5] ={ 0，2，3，4，0，0，7，0，0，0 y[] ={0，2，3，4，0，0，0 10y[10] := 10 (实际为：y[x[5]] := x[5])结果表：

y[] ={ 0，2，3，4，0，0，7，0，0，10 y[]={0，2，3，4，0，0，0，10 8y[8] := 8 (实际为：y[x[6]] := x[6])结果表：

y[] ={ 0，2，3，4，0，0，7，8，0，10等于9y[9] := 9 (实际为：y[x[7]] := x[7])结果表：

y[] ={ 0，2，3，4，0，0，7，8，9，10 }

• x[8]等于1y[1] := 1 (实际为：y[x[8]] := x[8])结果表：

y[] ={ 1，2，3，4，0，0，7，8，9，10等于6y[6] := 6 (实际为：y[x[9]] := x[9])结果表：

y[] ={ 1，2，3，4，0，6，7，8，9，10 }

• The y[]x[10] 5y[5] := 5 (实际为：y[x[10]] := x[10])结果表：

y[] ={ 1，2，3，4，5，6，7，8，9，10 }

正如我们所看到的，表y是输入表x的完全排序版本，它是通过10次迭代生成的(所以O(n)成本级别)。无论n有多大，以及给定的输入表有多无序，在采用这些特定假设的情况下，成本都是恒定的，并且等于n；

我希望我没有误解你的问题。

因为你已经知道了结果，所以我不清楚你是在什么意义上对任何东西进行“排序”。您在寻找什么结果--关于在每次迭代中“收集”哪些数字的信息，如您在Q中所示？在本例中，这里有一个简单的Python 2实现示例：

target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

def do_permut(targ):
    look_for = 1
    iter_num = 1
    while look_for != len(targ) + 1:
        print 'Iteration', iter_num, ':',
        for item in targ:
            if item == look_for:
                print item,
                look_for += 1
        print
        iter_num += 1

do_permut(target)

然而，任务不可避免地是O(N平方) --记住，大O代表最坏的情况！您将在N个数字上进行最多N次迭代(最坏的情况是在开始对targ进行反向排序时) --因此，N的平方。您可以通过收集之前在迭代过程中看到的一组数字并在look_for在该集合中时中断，对每次迭代进行轻微的optimize，但这只(大致)使每次迭代的工作量减半，因此它仍然是O(N平方)。

如果您能更好地解释您希望从您的工作中获得什么结果和输出，我们可能会提供更多帮助！

出于好奇，这里有一个具有上述“改进”的版本，并且还进行了健全性检查，以确保它会引发异常，而不是永远循环，如果传递的序列不是[1:n)的排列...：

target = 3, 7, 4, 2, 10, 8, 9, 1, 6, 5

def do_permut(targ):
    look_for = 1
    iter_num = 1
    while look_for != len(targ) + 1:
        print 'iteration', iter_num, ':',
        seen = set()
        found_in_iter = 0
        for item in targ:
            seen.add(item)
            if item == look_for:
                print item,
                found_in_iter += 1
                look_for += 1
                if look_for in seen:
                    break
        print
        if not found_in_iter:
            raise ValueError('missing: %s' % look_for)
        iter_num += 1

do_permut(target)