的＆QUOT的最小数量;插入＆QUOT;到一个数组排序 [英] The minimum number of "insertions" to sort an array

问题描述

假设有一个无序列表。我们唯一可以做的操作是将一个元素，将其插回到任何地方。有多少移动它把整个列表进行排序？

Suppose there is an unordered list. The only operation we can do is to move an element and insert it back to any place. How many moves does it take to sort the whole list?

我想答案是列表的大小。 - 最长有序的大小，但我不知道如何来证明这一点。

I guess the answer is size of the list - size of longest ordered sequence, but I have no idea how to prove it.

推荐答案

首先要注意运动的元素不会改变的元素比一个其他的相对顺序移动。

First note that moving an element doesn't change relative order of elements other than the one being moved.

考虑最长不下降子（密切相关的最长递增子 - 的方式找到它们是相似的）。

Consider the longest non-decreasing subsequence (closely related to the longest increasing subsequence - the way to find them are similar).

通过唯一的运动元素不会在这个序列中，可以很容易地看到，我们会最终有一个排序的列表，因为在这个序列中的所有元素都已经按彼此相对。

By only moving the element not in this sequence, it's easy to see that we'd end up with a sorted list, since all the elements in this sequence are already sorted relative to each other.

如果我们不移动的任何元件在这种序列中，在该子序列的两个元素之间的任何其他元件被保证是要么比中较小的一个大于较大的元素，或更小（如果这是不正确的，它本身将在最长序列），因此它需要移动。
（请参见下面的例子）

If we don't move any elements in this sequence, any other element between two elements in this subsequence is guaranteed to be either greater than the larger element, or smaller than the smaller one (if this is not true, it itself would be in the longest sequence), so it needs to be moved.
(see below for example)

是否需要是不降低？是。试想，如果在这个序列中的两个连续元素正在下降。在这种情况下，这将是不可能的，没有移动这两个因素的列表进行排序。

Does it need to be non-decreasing? Yes. Consider if two consecutive elements in this sequence are decreasing. In this case it would be impossible to sort the list without moving those two elements.

要最大限度地减少所需的移动次数，这是足够的挑选最长的序列不可能的，因为做了以上。

To minimize the number of moves required, it's sufficient to pick the longest sequence possible, as done above.

所以所需移动的总数是所述列表的大小减去最长非递减子序列的大小

So the total number of moves required is the size of the list minus the size of the longest non-decreasing subsequence.

一个例子说明一个元素的值不能在非递减序列上面提到的：

考虑最长不下降子 1 XX 2 XX 2×4 （即 X 的一些元素序列的一部分）。

Consider the longest non-decreasing subsequence 1 x x 2 x x 2 x 4 (the x's are some elements not part of the sequence).

现在考虑的可能值的 X 2 和 4 。

Now consider the possible values for an x between 2 and 4.

如果它是2，3或4，最长序列将包括该元素。如果是大于 4 或小于 2 更小，它需要被感动。

If it's 2, 3 or 4, the longest subsequence would include that element. If it's greater than 4 or smaller than 2, it needs to be moved.

这篇关于的＆QUOT的最小数量;插入＆QUOT;到一个数组排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！