为何.NET List.Sort返回0时原列表顺序仍发生改变？

这是个非常容易踩的坑！我当初刚接触.NET的时候也犯过同样的错误——默认的List<T>.Sort方法不是稳定排序算法，哪怕你的比较器返回0（表示两个元素相等），它们的相对位置也不会和原列表保持一致。

为什么会这样？ #

List<T>.Sort底层用的是快速排序（Quicksort），这种算法的特性就是不稳定：当两个元素被判定为“相等”时，排序过程中它们的位置可能会被交换，完全不考虑原始顺序。只有稳定排序算法才会在元素相等时保留它们的原始相对位置，而快速排序不在此列。

先说说你代码里的小问题 #

看你这段比较逻辑：

if (minMaxDate1.HasValue && !minMaxDate2.HasValue) return -1;
if (minMaxDate2.HasValue && !minMaxDate1.HasValue) return -1;

第二个判断明显有问题！如果game2有日期限制而game1没有，你应该返回1，这样game2会被排到game1前面；现在返回-1会导致无限制的元素反而排在有限制的前面，这大概率不是你想要的结果。

解决方案：用稳定排序替代 #

如果你需要在元素“相等”时保留原始顺序，推荐使用LINQ的OrderBy方法——它的实现是稳定排序，当两个元素的排序键相等时，会严格保留它们在原集合中的相对位置。

把你的代码改成这样：

games = games.OrderBy(game => {
    DateTime? minMaxDate = null;
    minMaxDate = FindDateRestriction(autoSchedulerLists, game.AwayTeam, minMaxDate);
    minMaxDate = FindDateRestriction(autoSchedulerLists, game.HomeTeam, minMaxDate);
    // 把无日期限制的元素排到最后，有值的按日期升序排
    return minMaxDate ?? DateTime.MaxValue;
}).ToList();

这样既实现了你的排序逻辑：

• 有日期限制的元素排在无限制的前面
• 都有日期限制的按日期升序排列
• 排序键相等的元素会保留原始顺序

补充说明 #

如果你一定要用Sort方法实现稳定排序，也可以自己实现一个稳定排序算法（比如归并排序），但显然用LINQ的OrderBy更简单高效，没必要重复造轮子。

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