假设有一个无序列表。我们唯一能做的操作就是移动一个元素并将其插入回任何位置。对整个列表进行排序需要多少步？
我想答案是size of the list - size of longest ordered sequence，但我不知道如何证明这一点。
首先请注意，移动元素不会改变除被移动元素之外的元素的相对顺序。
考虑最长的非递减子序列（与最长递增子序列- 找到它们的方式是相似的）。
通过仅移动不在此序列中的元素，很容易看到我们最终会得到一个排序列表，因为此序列中的所有元素都已相对于彼此排序。
如果我们不移动该序列中的任何元素，则该子序列中两个元素之间的任何其他元素都保证大于较大的元素，或小于较小的元素（如果这不成立，则它本身将位于最长的序列），因此需要移动它。
（例如见下文）
它必须是非递减的吗？是的。考虑该序列中的两个连续元素是否在递减。在这种情况下，如果不移动这两个元素，就不可能对列表进行排序。
为了最大限度地减少所需的移动次数，选择最长的序列就足够了，如上所述。
因此，所需的移动总数是列表的大小减去最长非递减子序列的大小。
一个例子解释不在上述非递减子序列中的元素的值：
考虑最长的非递减子序列1 x x 2 x x 2 x 4 (the x是一些不属于序列的元素）。
现在考虑一个可能的值x之间2 and 4.
如果是 2、3 或 4，则最长的子序列将包含该元素。如果它大于4或小于2，需要移动它。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
