WPF中如何为IList<T>实现O(log(n))时间复杂度的通用有序插入？

刚好在WPF开发中碰到过完全一样的需求——要给ObservableCollection保持有序，又不想每次插入都全量排序。你提到的二分法思路完全正确，这确实是最高效的方案：用二分查找O(log n)定位到正确的插入索引，再调用IList的Insert方法（这一步的时间复杂度是O(n)，因为IList底层如果是数组实现的话，插入需要移动后续元素，但这是IList本身的特性，没法绕过）。

下面是我整理好的通用静态扩展方法，直接就能用，支持默认比较和自定义比较器两种场景：

using System;
using System.Collections.Generic;

public static class SortedListExtensions
{
    /// <summary>
    /// 将元素插入到已排序的IList<T>中的正确位置，保持列表有序
    /// </summary>
    /// <typeparam name="T">列表元素类型</typeparam>
    /// <param name="list">已排序的IList<T></param>
    /// <param name="item">要插入的元素</param>
    public static void InsertInSortedOrder<T>(this IList<T> list, T item) where T : IComparable<T>
    {
        if (list == null) throw new ArgumentNullException(nameof(list));
        
        int index = FindInsertIndex(list, item, Comparer<T>.Default);
        list.Insert(index, item);
    }

    /// <summary>
    /// 使用自定义比较器，将元素插入到已排序的IList<T>中的正确位置
    /// </summary>
    /// <typeparam name="T">列表元素类型</typeparam>
    /// <param name="list">已排序的IList<T></param>
    /// <param name="item">要插入的元素</param>
    /// <param name="comparer">自定义比较器</param>
    public static void InsertInSortedOrder<T>(this IList<T> list, T item, IComparer<T> comparer)
    {
        if (list == null) throw new ArgumentNullException(nameof(list));
        if (comparer == null) throw new ArgumentNullException(nameof(comparer));
        
        int index = FindInsertIndex(list, item, comparer);
        list.Insert(index, item);
    }

    /// <summary>
    /// 二分查找找到元素应该插入的索引
    /// </summary>
    private static int FindInsertIndex<T>(IList<T> list, T item, IComparer<T> comparer)
    {
        int low = 0;
        int high = list.Count;

        while (low < high)
        {
            int mid = low + (high - low) / 2; // 避免整数溢出
            int comparisonResult = comparer.Compare(list[mid], item);
            
            if (comparisonResult < 0)
            {
                low = mid + 1;
            }
            else
            {
                high = mid;
            }
        }

        return low;
    }
}

使用示例 #

比如在WPF中操作ObservableCollection：

// 初始化一个有序的ObservableCollection
var sortedCollection = new ObservableCollection<int> { 1, 3, 5, 7 };

// 插入元素，自动放到正确位置
sortedCollection.InsertInSortedOrder(4);
// 现在集合是 {1, 3, 4, 5, 7}

// 自定义类型的情况，比如一个Person类实现IComparable<Person>
public class Person : IComparable<Person>
{
    public string Name { get; set; }
    public int Age { get; set; }

    public int CompareTo(Person other)
    {
        if (other == null) return 1;
        return Age.CompareTo(other.Age);
    }
}

// 使用示例
var people = new ObservableCollection<Person>
{
    new Person { Name = "Alice", Age = 25 },
    new Person { Name = "Bob", Age = 30 }
};

people.InsertInSortedOrder(new Person { Name = "Charlie", Age = 27 });
// 现在集合按Age排序：Alice(25), Charlie(27), Bob(30)

注意事项 #

• 调用这个方法前必须确保列表已经是有序的，否则插入位置会错误，导致后续集合无序
• 如果元素类型没有实现IComparable，一定要传入自定义的IComparer，否则会抛出异常
• 对于ObservableCollection，调用Insert方法会自动触发CollectionChanged事件，完美适配WPF的UI绑定，不需要额外处理
• 插入操作的整体时间复杂度：二分查找是O(log n)，IList.Insert是O(n)（因为要移动元素），这已经是基于IList的最优方案了——毕竟IList不像SortedList那样是基于二叉树或其他结构实现的快速插入

内容的提问来源于stack exchange，提问作者Eric Ouellet