如何修改基于Radix Sort的LINQ自定义方法以返回排序后的源列表

问题 #

为了追求极低时间复杂度，计划基于**基数排序（Radix Sort）**实现类似LINQ .OrderBy()的自定义排序方法，期望调用方式如下：

var sortedListOfAppointments = listOfAppointments.OrderByDateUsingRadixSort(a => a.AppointmentDateTime);

目前已实现SortDatesUsingRadixSort方法可对IEnumerable<DateTime>进行排序，同时实现了泛型方法OrderByDateUsingRadixSort，但该方法仅返回排序后的日期列表，而非排序后的源对象列表。原方法代码如下：

public static IEnumerable<TSource> OrderByDateUsingRadixSort<TSource>(this IEnumerable<TSource> dates, Func<TSource, DateTime> selector) =>
    // 需修改此处以返回排序后的完整列表
    (from date in dates select selector(date)).SortDatesUsingRadixSort();

需要修改该泛型方法，使其返回IEnumerable<TSource>类型的排序结果。

解决方案 #

核心思路是保留源对象与对应日期的关联关系，先维护"源对象-日期"的绑定结构，排序后再提取源对象。以下是两种可行的修改方案：

方案1：基于现有SortDatesUsingRadixSort适配 #

如果不想改动已实现的SortDatesUsingRadixSort，可以通过记录原始索引来处理重复日期的匹配问题，代码如下：

public static IEnumerable<TSource> OrderByDateUsingRadixSort<TSource>(this IEnumerable<TSource> source, Func<TSource, DateTime> selector)
{
    // 将源元素、对应日期、原始索引绑定，避免重复日期导致匹配错误
    var indexedItems = source.Select((item, index) => new { Item = item, Date = selector(item), OriginalIndex = index }).ToList();
    
    // 提取日期并排序
    var sortedDates = indexedItems.Select(x => x.Date).SortDatesUsingRadixSort().ToList();
    
    // 按排序后的日期匹配源对象，用原始索引标记已使用元素
    var sortedItems = new List<TSource>();
    var usedIndices = new HashSet<int>();
    
    foreach (var date in sortedDates)
    {
        var match = indexedItems.First(x => x.Date == date && !usedIndices.Contains(x.OriginalIndex));
        sortedItems.Add(match.Item);
        usedIndices.Add(match.OriginalIndex);
    }
    
    return sortedItems;
}

方案2：优化SortDatesUsingRadixSort提升效率 #

如果可以修改SortDatesUsingRadixSort，让它返回带原始索引的排序结果，能大幅降低匹配环节的时间开销，更贴合基数排序的低复杂度优势：

1. 先修改SortDatesUsingRadixSort，使其返回包含日期和原始索引的序列，比如IEnumerable<(DateTime Date, int OriginalIndex)>；
2. 再调整泛型方法：

public static IEnumerable<TSource> OrderByDateUsingRadixSort<TSource>(this IEnumerable<TSource> source, Func<TSource, DateTime> selector)
{
    var sourceList = source.ToList();
    // 生成日期与原始索引的配对
    var dateIndexPairs = sourceList.Select((item, index) => (Date: selector(item), Index: index));
    // 调用修改后的基数排序方法，得到排序后的配对序列
    var sortedPairs = dateIndexPairs.SortDatesUsingRadixSort();
    
    // 直接通过索引从源列表中提取排序后的元素
    return sortedPairs.Select(pair => sourceList[pair.Index]);
}

这种方式的时间复杂度更接近基数排序本身的O(nk)（n为元素数量，k为日期的基数位数），完全符合低复杂度的需求。

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