javascript - 算法:将列表从一个顺序重新排列到另一个顺序的最佳方法？

Question

编辑: 我不确定我原来的问题是否足够清楚。我需要一种算法来计算最小的移动顺序，以将数组从一个顺序重新排列到另一个顺序。众所周知，两个数组将包含相同的元素(无重复项)并且具有相同的长度。例如:

reorder(
  ['d', 'a', 'c', 'b', 'e'],
  ['a', 'b', 'c', 'd', 'e']
)

应该返回如下内容:

[
  {move:'d', after:'b'},
  {move:'c', after:'b'}
]

这表明我应该先将元素“d”移动到“b”之后，然后将“c”移动到“b”之后，数组将按所需顺序排列。

---

背景:我正在做一个项目(实际上是将 rtgui 中的大部分功能移至客户端)。现在我正在处理排序。基本上我有一个要按任意顺序排序的 div 列表。我可以按如下方式获得所需的顺序:

var hashes = {
  before: [],
  after: [],
};
var els = $('div.interesting-class').toArray();
var len = els.length;

for(var i = 0; i < len; i++) hashes.before.push(els[i].id);
els.sort(getSortComparator());
for(var i = 0; i < len; i++) hashes.after.push(els[i].id);

现在 hashes.before 和 hashes.after 包含元素 ID 的无序列表和有序列表。在重新排序列表时，到目前为止，最昂贵的操作实际上是移动 DOM 元素。我一直这样做如下:

var c = $('#container-id');
$(els).each(function() {
  c.append(this);
});

这可行，但比必要的要慢，因为平均而言，真正需要移动的元素只有 2 或 3 个。因此，我需要一种算法来计算将数组从一个顺序重新排列到另一个顺序的最小移动顺序(在本例中，对 hashes.before 和 hashes.after).任何人都可以提出一个建议或提出任何想法吗？

到目前为止，我已经尝试了几种通用的“差异”算法，但它们并没有真正满足我的需求。我想我需要的是那样，但更专业。

Answer 1

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

找到最长的递增子序列(根据新的排序顺序)。然后将不在该序列中的每个元素移动到相对于序列中已有元素的位置。

在您的示例中，'a, b, e' 和 'a, c, e' 与最长递增子序列相关联。您最多只能选择其中一个元素，然后移动其他元素。