按最小移动次数排序数组

Question

理论上可以通过只移动未按排序顺序排列的元素来对length（array）-length（longestIncreasingSubsequence（array））中的数组进行排序。

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ]

最长的递增子序列为：

[ 1, 2, 4, 6, 7, 10 ]

这些要素的指数如下：

[ 0, 3, 4, 5, 8, 9 ]

因此，我们需要移动的指数是：

[ 1, 2, 6, 7]

[ 7, 4, 2, 8]

Answer 1

您的问题是源位置是以前面的顺序表示的，而目标位置是以最后的顺序表示的。当你做1->7时，你还不知道7在前面的顺序中的位置。你需要为所有的动作做出调整。

原来的招式是：

from: [ 1, 2, 6, 7]
to:   [ 7, 4, 2, 8]

步骤1

from: [ 1, 1, 4, 4]

to:   [ 5, 3, 2, 8]

步骤2

我们有的是正确的位置为4个移除，然后是4个插入。现在我们要交错删除和插入。

在（1,1,4）处拆卸之前，必须先插入（5）处。5比其中任何一个都大，所以它不会影响位置(1，1，4)，但是5会受到影响，因为3个移除是在插入点左侧完成的。5变成8。

for i = 0 to size-1
    for j = size-1 to i+1
        if from[j] < to[i] then increment to[i]
        else increment from[j]

我们应该得到数组：

from: [ 1, 1, 5, 6]
to:   [ 8, 3, 2, 8]

这些是在移动时以正确的位置执行的最后移动。移动可以从左到右读取：在1处移除，在8处插入。在%1处拆下，在%3处插入。在5处拆下，在2处插入。在6处拆下，在8处插入。