C#中如何在不排序原主列表的前提下按字母顺序合并两个List<string>
实现方案
核心逻辑
- 核心约束:全程不对主列表list1做任何重排、全局排序操作,严格保留list1原有元素的相对前后顺序。
- 执行流程:
- 先对待插入的list2做升序字典序排序,保证待插入元素从小到大依次处理
- 维护一个游标,标记list2中尚未插入的元素的起始位置
- 按原始顺序遍历list1的每一个元素,先把list2中所有字典序小于当前主元素、尚未插入的元素逐个加入合并结果,再追加当前的主列表元素
- 全部遍历完list1的元素后,把list2中剩余的未插入元素(均大于所有主列表元素)直接追加到合并结果末尾
完整代码实现
// 初始化测试数据 List<string> list1 = new List<string> { "AB2", "AB1", "AB3", "BB3", "BB2", "BB1" }; List<string> list2 = new List<string> { "AA1", "AA2", "BA1", "BA2" }; // 对待插入列表按纯Unicode字符序升序排序 list2.Sort(StringComparer.Ordinal); List<string> mergedList = new List<string>(list1.Count + list2.Count); int insertCursor = 0; int list2Length = list2.Count; // 按原顺序遍历主列表,构建合并结果 foreach (string currentMainItem in list1) { // 插入所有字典序小于当前主元素的待插入元素 while (insertCursor < list2Length && string.CompareOrdinal(list2[insertCursor], currentMainItem) < 0) { mergedList.Add(list2[insertCursor]); insertCursor++; } // 追加当前主列表元素,确保主列表元素相对顺序不变 mergedList.Add(currentMainItem); } // 追加剩余的待插入元素(均大于所有主列表元素) while (insertCursor < list2Length) { mergedList.Add(list2[insertCursor]); insertCursor++; }
效果验证
代码运行后生成的mergedList结果为:["AA1", "AA2", "AB2", "AB1", "AB3", "BA1", "BA2", "BB3", "BB2", "BB1"]
和示例要求的合并结果完全一致:主列表中AB2在AB1之前、BB3在BB2之前的原始相对顺序没有任何改动,待插入元素全部按字典序落在了正确的位置。
注意事项
- 字符串对比默认使用
StringComparer.Ordinal实现纯字符码点的字典序排序,和示例输出完全匹配;如果需要适配当前系统文化的本地化排序规则(比如处理带重音、特殊符号的字符),可将排序、比较逻辑替换为对应文化的字符串比较器。 - 实现过程全程不修改原
list1、list2的内容,仅生成新的合并列表,不会对原有数据造成意外篡改。 - 时间复杂度为
O(m log m + n),其中m为list2的长度,n为list1的长度,相比全量排序的实现方式效率更高,且完全满足不改动主列表原有顺序的核心要求。 - 覆盖所有边界场景:当list1为空时直接返回排序后的list2;当list2为空时直接返回原list1的所有元素;待插入元素小于所有主元素时自动插到列表最前端,大于所有主元素时自动追加到列表最末端。
内容的提问来源于stack exchange,提问作者man-teiv
相关产品推荐
相关产品推荐

