c# - SortedList 性能 - 排序列表如何自行排序？

Question

我试图找出有关排序列表的更多详细信息，以便我可以分析它是否会像我需要的那样在几种特定情况下执行。

有谁知道它用于对其元素进行排序的特定排序算法？

Answer 1

SortedList<T,U>在内部使用一个数组作为其键，并通过Add以正确的顺序插入项目来执行“排序”。当您Add使用新项目调用时，它会Array.BinarySearch使用Array.Insert.

这就是它具有以下特点的原因：

此方法是对未排序数据的 O(n) 操作，其中 n 是 Count。如果将新元素添加到列表的末尾，则这是一个 O(log n) 操作。如果插入导致调整大小，则操作为 O(n)。