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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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）。谁能建议一个或提出任何想法？

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

回答：

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

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

在您的示例中，“ a，b，e”和“ a，c，e”并列为最长的递增子序列。您能做的最好的事情就是选择其中之一，然后移动其他元素。

以上是 算法：将列表从一个顺序重新排列到另一个顺序的最佳方法？ 的全部内容， 来源链接： utcz.com/qa/400571.html

回到顶部