在int列表中插入值并排序的最快方法

Question

我正在使用动态整数泛型列表。我试图添加并按降序排序该列表。这个操作会多次发生。 目前，我正在使用Linq来完成此操作。

list.Add(b);
list = list.OrderByDescending(i => i).ToList();

有没有办法全面提高这个操作的性能。

- Jasmeet

---

你可以使用 SortedDictionary 或 SortedSet。 - Valentin

或者一个 SortedList……如果你没有重复的值，那么 SortedSet 可以帮助。 - Zohar Peled

@ZoharPeled SortedList 也不允许重复。 - Sergey Kalinichenko

Answer 1

您目前的做法是次优的，因为每次添加一个元素时，您都会再次对整个列表进行排序，这可以避免，并且每次将整数添加到List中时，都会构造一个新列表，这也可以避免。

由于您已经有了一个List，我建议使用属于该类的方法，而不是使用LINQ来避免开销。

我的建议是创建一个扩展方法，如下所示：

public static class Extensions {
        public static void InsertElementDescending(this List<int> source, 
                int element)
        {
            int index = source.FindLastIndex(e => e > element);
            if (index == 0 || index == -1)
            {
                source.Insert(0, element);
                return;
            }
            source.Insert(index + 1, element);
        }
}

那么使用情况将是这样的：

List<int> list = new List<int>();

list.InsertElementDescending(1);
list.InsertElementDescending(2);
list.InsertElementDescending(233);
list.InsertElementDescending(0);
list.InsertElementDescending(-2);

• 该列表现在将按降序排列元素。
• 总体而言，这比您目前的方法性能更好。

- Ousmane D.

Answer 2

你的方法确实存在很多开销，因为每次插入都会创建一个新的 List<T>。

你可以通过就地排序来加速。考虑在原始预排序列表的末尾添加项目后，你所需要做的就是将该项目向后移动，直到遇到一个大于新插入项的项目。你可以这样做：

static void InsertSorted<T>(IList<T> list, T item) where T : IComparable<T> {
    list.Add(item);
    var i = list.Count-1;
    for ( ; i > 0 && list[i-1].CompareTo(item) < 0 ; i--) {
        list[i] = list[i-1];
    }
    list[i] = item;
}

演示。

- Sergey Kalinichenko