C#锯齿数组按规则排序后Array.Sort与Linq结果差异原因

核心差异原因 #

1. 排序稳定性不同
   Array.Sort 默认采用不稳定排序算法（如快速排序），即使两个元素的比较结果为"相等"（比较器返回0），排序过程也可能交换它们的相对位置，破坏原数组中的索引顺序。而Linq的OrderBy是稳定排序，当元素比较结果相等时，会严格保留它们在原数组中的先后顺序。

2. IComparer无法获取原索引
   你的排序规则要求：当array[i][0] == array[j][0]时，按原数组索引i-j排序（原索引小的元素在前）。但直接使用IComparer<int[]>时，比较器只能访问元素本身，无法获取该元素在原数组中的原始索引——这意味着你根本没法在IComparer里完整实现你的排序规则。如果你的比较器在元素array[0]相等时返回0，Array.Sort就会认为这些元素可以任意交换，最终导致顺序混乱。

正确实现方式 #

方式一：使用Linq（推荐，符合需求） #

通过Select绑定元素与原索引，再按规则排序，完美满足要求：

int[][] arr = new int[][] { new int[] {2}, new int[] {1}, new int[] {2}, new int[] {2} };
var sortedArr = arr
    .Select((item, index) => new { Item = item, OriginalIndex = index })
    .OrderBy(x => x.Item[0])
    .ThenBy(x => x.OriginalIndex)
    .Select(x => x.Item)
    .ToArray();

方式二：用Array.Sort实现（若必须使用Array.Sort） #

先将元素与原索引包装成新对象，排序后再提取元素：

int[][] arr = new int[][] { new int[] {2}, new int[] {1}, new int[] {2}, new int[] {2} };
// 包装元素与原索引
var indexedElements = arr.Select((item, idx) => new { Item = item, Index = idx }).ToArray();

// 按规则排序包装后的数组
Array.Sort(indexedElements, (a, b) => {
    int valueCompare = a.Item[0].CompareTo(b.Item[0]);
    if (valueCompare != 0)
        return valueCompare;
    // 相等时按原索引排序
    return a.Index.CompareTo(b.Index);
});

// 提取排序后的元素
arr = indexedElements.Select(x => x.Item).ToArray();

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