algorithm - "insertions"对数组排序的最小个数

Question

假设有一个无序列表。我们唯一能做的操作就是移动一个元素并将其插入回任何地方。对整个列表进行排序需要多少步？

我猜答案是size of the list - size of the longest ordered sequence，但我不知道如何证明它。

Answer 1

首先请注意，移动元素不会改变被移动元素以外的元素的相对顺序。

考虑最长的非递减子序列(与 the longest increasing subsequence 密切相关 - 找到它们的方法类似)。

只移动不在这个序列中的元素，很容易看出我们最终得到一个排序列表，因为这个序列中的所有元素已经相对于彼此排序。

如果我们不移动这个序列中的任何元素，那么这个子序列中两个元素之间的任何其他元素都保证大于较大的元素，或者小于较小的元素(如果这不是真的，它本身将在最长的序列中)，因此需要移动它。
(例如见下文)

是否需要非递减？是的。考虑这个序列中的两个连续元素是否在递减。在这种情况下，如果不移动这两个元素就不可能对列表进行排序。

为了尽量减少所需的移动次数，选择最长的序列就足够了，就像上面所做的那样。

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

一个不在上述非递减子序列中的元素值的例子:

考虑最长的非递减子序列 1 x x 2 x x 2 x 4(x 是一些不属于序列的元素)。

现在考虑 2 和 4 之间的 x 的可能值。

如果是 2、3 或 4，最长的子序列将包含该元素。如果大于4或小于2，则需要移动。