3

我正在使用 OrderBy 方法对包含 10,000 个元素的字典进行排序，如下所示，并且想知道它的大 O。有人知道吗？订购它们后，我按该顺序将它们添加到新字典中。可能有更好的方法来做到这一点，但它适用于我的目的。

这是我的例子：

        m_sortedItems = new Dictionary<int,string>();
        foreach(KeyValuePair<int,string> item in collection.OrderBy(key => key.Value)){
            m_sortedItems.Add(item.Key, item.Value);
        }

我检查了 msdn，但没有列出：http: //msdn.microsoft.com/en-us/library/bb534966.aspx

4

2 回答 2

6

在常规字典中添加排序集合是没有意义的，因为字典不能保证保持顺序。这只是不鼓励您在问题中显示的代码：它可能在某些情况下有效，但相信我这是不正确的。有必要指出这样一个事实，即通过将有序集添加回字典只会使您之前所做的排序无效。您可以按某种顺序枚举 KeyValuePairs 并添加到常规列表中，这将保留插入顺序，或者更好地使用其他一些数据结构。看看排序字典的例子. 当然，这种数据结构在插入阶段需要更多时间，而排序通常很快，因为它们是“自然”排序的。根据文档，排序字典插入时间“充其量” O(log(n))，我建议您也调查几乎有序输入集的性能，因为有时基于树的数据结构会由于不平衡的树形成而遭受这种情况. 如果是这种情况（我不知道内部是如何实现的）并且性能变得至关重要，那么另一个有趣的数据结构是 B-Tree。

于 2012-10-12T18:15:38.463 回答
3

字典没有定义顺序，因此按特定顺序添加项目不是您应该做的事情。

就排序的大 O 而言，O(NlogN) 将成为您将遇到的大多数排序算法的基准。

于 2012-10-12T18:15:39.687 回答