c# - Linq OrderBy().ThenBy() 方法序列的时间复杂度是多少？

Question

我在我的项目中使用 Linq 和 Lambda 操作，我需要根据类的两个属性对列表进行排序。因此，我使用了 OrderBy().ThenBy() 方法如下:

class ValueWithIndex{
    public long Value;
    public int Index;
}
...

List<ValueWithIndex> valuesWithIndex = new List<ValueWithIndex>();

for (int i = 0; i < A.Length; i++){
    ValueWithIndex vi = new ValueWithIndex();
    vi.Value = A[i];
    vi.Index = i;
    valuesWithIndex.Add(vi);
}
var orderedValues = valuesWithIndex.OrderBy(v => v.Value).ThenBy(v => v.Index);

...

在This回答中解释说，OrderBy()使用Quicksort，所以即使它有O(N*logN)的平均时间复杂度，最坏的情况下，时间复杂度也在O(N²)左右。如果 ThenBy() 方法的最差时间复杂度为 O(N²)，则使用这些方法将毫无意义。

ThenBy() 方法也使用快速排序吗？如果是，是否意味着对于相同的“v.Value”，“v.Index” es 以 O(N²) 最差时间复杂度排序？

Answer 1

LINQ OrderBy(...).ThenBy(...)...ThenBy(...) 方法链通过< strong>多个排序键(使用多键比较器)。

因此，无论您在链中包含多少 ThenBy(Descending) 方法，排序操作的时间复杂度都保持在 QuickSort O(N*logN) 平均/O( N²) 最坏情况。当然你添加的键越多，比较两个对象会花费更多的时间，但是排序操作的复杂度不会改变。