链表python的最小写入排序

Question

我有一个链表：1 3 7 4 5 0 2 6。我希望以最少的移动/写入次数对其进行排序。你知道吗

我只能使用函数insertBetween(element, after, before)移动该列表的元素，该函数只是在after和before元素之间插入element。你知道吗

例如，第一次运行可能希望将1移到0之后2之前： insertBetween(1, 0, 2)

列表现在将是3 7 4 5 0 1 2 6。你知道吗

现在它可能想把7移到末尾：insertBetween(7, 6, None)

列表现在将是3 4 5 0 1 2 6 7。你知道吗

现在它可能想把0移到开头：insertBetween(0, None, 3)

列表现在将是0 3 4 5 1 2 6 7。你知道吗

这种排序算法的唯一优先权是使用函数insertBetween(element, after, before)的次数最少，因为使用它非常昂贵。我希望用Python实现它。你知道吗

Answer 1

不要把注意力集中在你移动的元素上。它们可以移动到任何地方，不是问题。相反，把注意力集中在你不移动的元素上。这些需要已经分类了。如果你有N个元素和一个长度为L的最长排序子序列，你只需要N-L个移动来移动不在这个子序列中的N-L个元素，你做得再好不过了。寻找排序最长的子序列是一个标准问题，但是look here如果你不知道怎么做的话。你知道吗