以最少的次数将数组排序

Question

以最少的次数将数组排序

6

理论上可以通过只移动未排序的元素，在 length(array) - length(longestIncreasingSubsequence(array)) 步内将数组排序。

如果唯一允许的操作是原地移动，即每次仅移动一个元素，通过从索引 A 删除一个元素并重新插入到索引 B 中，如何生成正确的移动步骤以获得排序后的数组？同样，需要执行 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]

因为这些索引目前没有按照顺序排列，所以需要进行排序。

为了得到一个有序数组，这4个元素的最终索引为：

[ 7, 4, 2, 8]

因此，我们需要同时将索引1移动到索引7，将索引2移动到索引4，将索引6移动到索引2，并将索引7移动到索引8。问题在于，当一个元素被移动时，其他元素会发生移位，从而使后面的移动操作变得无效。我尝试过转换这些索引，但迄今为止还没有得出所需的正确移动列表。有什么想法吗？希望我已经解释清楚了问题。请提问，我会澄清的。谢谢！

- devongovett

你是如何“转换索引”的？如果在交换 1<>7 后，您将所有对 7 的前向引用替换为 1，反之亦然，则 7<>8 将变为 1<>8，这三个值将处于正确的位置。 - Ian Mercer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Florian F · Accepted Answer

你的问题在于源位置按照先前顺序表达，而目标位置按照最终顺序。当你执行1->7时，你还不知道7在先前顺序中的位置。你需要为所有移动进行调整。

原始移动如下：

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

步骤1

首先，让我们将位置转换为好像我们首先移除了所有元素，然后将元素插入到新位置。对于from位置，请从左侧开始：在1处删除会将位置(2,6,7)下移至(1,5,6)。再次在1处删除将(5,6)下移至(4,5)。在5处删除将5下移至4。用from中的每个位置，所有具有较大或等于索引的后续位置都必须递减。我们得到：

from: [ 1, 1, 4, 4]

对于“to”位置，请从末尾开始：位置8是正确的。位置2也是正确的，但这意味着插入时先前的(7,4)实际上是(6,3)。所以我们调整它们。同样地，插入在3意味着先前的位置6位于5。

因此，对于“to”数组，我们从结尾开始，对于每个位置，我们会递减所有具有较大索引的先前位置。 “to”数组变为：

to:   [ 5, 3, 2, 8]

步骤2

我们现在已经确定了4个删除操作和4个插入操作的正确位置。接下来，我们要交错进行删除和插入操作。

在位置5进行插入必须在位置为（1、1、4）的删除操作之前完成。由于5比这些位置都大，所以它不会影响（1、1、4）的位置，但是5受到影响，因为3个删除操作在插入点左侧完成。5变成了8。

在位置3进行插入必须在位置为（4、4）的删除操作之前完成。由于3比4小，所以位置3不受删除操作的影响，但必须将删除操作增加到位置（5、5）。

在位置2进行插入必须在最后一个删除操作（原来的位置为5）之前完成。由于它比5小，因此5被调整为6。

步骤2的通用方法：

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。