使用最少的插入和删除数对 IList 重新排序

本文关键字：新排序 排序 IList 插入 删除 | 更新日期: 2023-09-27 18:32:43

我需要一个接受两个参数的扩展方法：一个目标IList<T>和一个自定义比较器。

public static void CustomSort<T>( IList<T> target, IComparer<T> comparer )
{
    ...
}

扩展方法的工作是按照自定义比较器指示的顺序排列目标的元素。

以下是一些不起作用的解决方案：

  • List<T>.Sort进行就地排序，这基本上是我所追求的。 但我不能假设目标的具体类型是List<T>.
  • LINQ 提供了一些解决方案，但遗憾的是，它们将结果输出为新的可枚举对象，而不是修改目标列表。

相反，我需要调用目标的Remove和Insert方法，以将其元素按正确的顺序排列。 目标列表可能是可观察的，因此重要的是解决方案不会执行超过获得所需顺序所需的删除和插入。

使用最少的插入和删除数对 IList<T> 重新排序

我认为这样的事情会让你。

我们对偏移量数组进行排序，然后确定需要应用的增量集，最后应用它们以生成新排序的 IList。

public static void CustomSort<T>( IList<T> list , IComparer<T> comparer )
{
  int[] unsorted = Enumerable.Range(0,list.Count).ToArray() ;
  int[] sorted   = Enumerable.Range(0,list.Count).OrderBy( x => list[x] , comparer ).ToArray() ;
  var   moves    = sorted.Zip( unsorted , (x,y) => new{ Src = x , Dest = y , } ).Where( x => x.Src != x.Dest ).OrderBy( x => x.Src ).ToArray() ;
  // at this point, moves is a list of moves, from a source position to destination position.
  // We enumerate over this and apply the moves in order.
  // To do this we need a scratch pad to save incomplete moves, where an existing item has
  // been over-written, but it has not yet been moved into its final destination.
  Dictionary<int,T> scratchPad = new Dictionary<int, T>() ; // a parking lot for incomplete moves
  foreach ( var move in moves )
  {
    T value ;
    // see if the source value is on the scratchpad.
    // if it is, use it and remove it from the scratch pad.
    // otherwise, get it from the indicated slot in the list.
    if ( scratchPad.TryGetValue( move.Src , out value ) )
    {
      scratchPad.Remove( move.Src );
    }
    else
    {
      value = list[ move.Src ] ;
    }
    // if the destination is after the source position, we need to put
    // it on the scratch pad, since we haven't yet used it as a source.
    if ( move.Dest > move.Src )
    {
      scratchPad.Add( move.Dest , list[ move.Dest ]);
    }
    // finally, move the source value into its destination slot.
    list[ move.Dest ] = value ;
  }
  return ;
}

如前所述，评论表明这实际上可能是一个难题。那么，如果我们从不同的角度看待这个问题呢：

  1. 为什么这个集合的观察者需要这么长时间？他们应该只做快速的事情来响应个人的变化。例如，如果是 UI 更改，它可以等到下一次 UI 重绘后再关心更改。这应该让整个重新排序一次性完成。或
  2. 使用类似 ObservableRangeCollection<T> 的内容，以便对可观察集合有AddRange。一些简单的代码可以确定集合是List<T>还是ObservableRangeCollection<T>使用AddRange（如果可能）。

例如

public static void SmartSort<T>(IList<T> source)
{
    var sortedList = source.OrderBy(x => x).ToList();
    if (source.SequenceEqual(sortedList))
        return;
    var list = source as List<T>;
    var collection = source as ObservableRangeCollection<T>;
    if (list != null)
    {
        list.Clear();
        list.AddRange(sortedList);
    }
    else if (collection != null)
        collection.ReplaceRange(sortedList);
    else
    {
        for (int i = 0; i < source.Count; i++)
            source[i] = sortedList[i];
    }
}

  1. 使用 LINQ 扩展方法进行排序并获取在末尾隐式调用ToList()的新 List;

  2. 然后告诉你的可观察列表挂起自己（不要关心更改）

  3. 清除可观察列表

  4. 将项从 linq 排序列表添加到可观察列表。

  5. 告诉您的可观察列表继续监视更改

它对可观察量手表的更改次数是有效的;从算法效率的角度来看，我会尝试这个解决方案。您可能永远不需要进一步优化。记住：过早优化是万恶之源

相关文章：