假设有一个无序列表。我们唯一可以做的操作是移动一个元素并将其插入到任何位置。对整个列表进行排序需要多少步？
我想答案是size of the list - size of longest ordered sequence，但是我不知道如何证明这一点。
首先要注意的是，移动元素不会改变元素的相对顺序，除了要移动的元素之外。
考虑最长非递减子（有密切关系最长递增子-找到它们是类似的方式）。
通过只移动不在此序列中的元素，很容易看到我们最终得到了一个排序列表，因为此序列中的所有元素都已经相对于彼此进行了排序。
如果我们不移动此序列中的任何元素，则保证此子序列中两个元素之间的任何其他元素大于或大于或小于较小的元素（如果不正确，则它本身将位于最长的序列），因此需要移动它。
（例如，参见下文）
是否需要不减少？是的。考虑此序列中的两个连续元素是否正在减少。在这种情况下，不移动这两个元素就不可能对列表进行排序。
为了最大程度地减少所需的移动次数，如上所述，选择尽可能长的序列就足够了。
因此，所需的移动总数为列表的大小减去最长的非递减子序列的大小。
一个示例，说明不在上述非递减子序列中的元素的值：
考虑最长的非递减子序列1 x x 2 x x 2 x 4（x的是某些元素，不属于序列的一部分）。
现在考虑x介于2和之间的可能值4。
如果是2、3或4，则最长的子序列将包含该元素。如果大于4或小于2，则需要移动它。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句