C#中如何按销量范围及同类聚合规则对零件列表高效排序

• 第一步：先执行初始的销量降序排序，保证全局主排序规则不被破坏，这一步时间复杂度为O(n log n)，是排序类需求的最优基准复杂度
• 第二步：遍历排序后的列表，为每个元素生成二级分组键：维护一个字典记录每个零件名称上一次出现的销量、对应分组的键值，当前元素如果和同名称上一次出现的销量差值≤100，就沿用该分组的键值，同时更新字典里该名称的最新销量；否则创建新分组，用当前元素的销量作为新分组的键值，同时更新字典记录
• 第三步：先按分组键降序排序，同分组内再按销量降序排序，即可得到符合要求的结果，这一步时间复杂度仍为O(n log n)

var parts = new List<(string name, int sales)>{
    ("Part A", 400),
    ("Part B", 600),
    ("Part A", 600),
    ("Part C", 400),
    ("Part D", 1500),
    ("Part B", 500),
    ("Part A", 475),
    ("Part B", 400),
    ("Part E", 700),
    ("Part A", 700),
};

// 第一步：按销量降序做初始排序
var sortedBySales = parts.OrderByDescending(p => p.sales).ToList();

// 字典存储：key=零件名，value=（上一次出现的销量，当前分组的键）
var groupInfoDict = new Dictionary<string, (int lastSales, int groupKey)>();
var elementsWithGroupKey = new List<(string name, int sales, int groupKey)>();

// 第二步：遍历生成分组键
foreach (var part in sortedBySales)
{
    if (groupInfoDict.TryGetValue(part.name, out var info))
    {
        // 和同名称上一个元素的销量差值在100以内，归入同一分组
        if (info.lastSales - part.sales <= 100)
        {
            elementsWithGroupKey.Add((part.name, part.sales, info.groupKey));
            groupInfoDict[part.name] = (part.sales, info.groupKey);
            continue;
        }
    }
    // 不符合聚合条件则新建分组
    groupInfoDict[part.name] = (part.sales, part.sales);
    elementsWithGroupKey.Add((part.name, part.sales, part.sales));
}

// 第三步：按分组键降序、同组内销量降序排序得到最终结果
var finalResult = elementsWithGroupKey
    .OrderByDescending(x => x.groupKey)
    .ThenByDescending(x => x.sales)
    .Select(x => (x.name, x.sales))
    .ToList();

• 整体时间复杂度稳定为O(n log n)，和基础排序操作的复杂度一致，没有额外的高开销运算，完全适配大数据量场景
• 空间开销仅为额外存储每个元素的分组键，以及存储每个零件最新分组信息的字典，内存占用可控
• 差值阈值支持灵活调整，仅需要修改info.lastSales - part.sales <= 100的判断条件即可

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