小编tun*_*luk的帖子

我在我的项目中使用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 ²)最差的时间复杂度？