假设一个数组，其中每个元素也是一个正整数，没有重复且没有任何缺失元素，如下所示:
{15, 1, 2, 6, 7, 8, 3, 4, 9, 5, 10, 13, 11, 12, 14}
考虑到每个元素的删除和插入(而不是交换)，我怎样才能找到最有效的移动(删除/插入)操作来以最少的插入次数对列表进行排序。
我认为识别各个组很有帮助，因为我可以更轻松地找到需要一起移动的内容:
{{15}, {1, 2}, {6, 7, 8}, {3, 4}, {9}, {5}, {10}, {13}, {11, 12}, {14}}
为此，我可以创建另一个包含值和正确位置之间差异的数组，以便我轻松识别组以及哪些组与正确位置最远。
{{14}, {-1, -1}, {2, 2, 2}, {-4, -4}, {0}, {-5}, {-1}, { 1}, {-2, -2}, {-1}}
然后我选择了离正确位置最远(最大差异)且元素数量较少的组。因此，基于此我可以看到 {15} 距离正确还有 14 个，应该是第一个被移动的。我认为(我在这里猜测)我至少需要移动值(value)差异，因为我可以落在小组中间。重复我将 {5} 移动到 {6,7,8} 之前的过程，它移动了 6 个空格，值和正确位置之间的差异更大，因为在正确的位置有一个组。然后是 {3,4}，最后是 {13}，列表已排序。
我已经可以创建一个迭代方法来做到这一点。但我认为这会非常低效，因为我将处理大约 200k 个值并在每组插入之后重新计算它是一个糟糕的主意。
PS:我需要遵循这个过程(删除和插入元素，分组思考)而不是其他更省时的方法，因为这将应用于现实世界中对货架上的元素进行分类，以及具有与计算或内存要求相比，较少项目的较少操作是首选。
最佳答案
最小化移动的元素数量与最大化不移动的元素数量相同。
由于您不移动的任何元素都将保留其原始顺序，因此这些元素必须是所需排序数组的子序列。您可以使用通用算法找到最长的此类子序列:
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
然后删除所有不属于该子序列的元素，并将它们重新插入到它们所属的位置。
请注意，您可以针对最长单调递增子序列的这种特定情况使用优化:
https://en.wikipedia.org/wiki/Longest_increasing_subsequence https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
关于arrays - 排序数组时最小化插入次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53871944/