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

Question

我在我的项目中使用Linq和Lambda Operations,我需要根据类的两个属性对List进行排序.因此,我使用了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);

...

在这个答案中,我们解释说,OrderBy()使用Quicksort,因此即使它具有O(N*logN)平均时间复杂度,对于最坏的情况,时间复杂度约为O(N ²).如果ThenBy()方法的时间复杂度最差为O(N ²),那么使用这些方法毫无意义.

ThenBy()方法也使用Quicksort吗？如果是,那是否意味着对于相同的"v.Value","v.Index"会被排序为O(N ²)最差的时间复杂度？

Answer 1

LINQ OrderBy(...).ThenBy(...)...ThenBy(...)方法链通过多个排序键(使用多键比较器)形成单个排序操作.

因此,无论ThenBy(Descending)您在链中包含多少方法,排序操作的时间复杂度仍然是QuickSort O(N*logN)平均值/ O(N ²)最差情况的典型时间.当然,您添加的更多键,比较两个对象将花费更多时间,但排序操作的复杂性不会改变.