Linq OrderBy（）。ThenBy（）方法序列的时间复杂度是多少？

我在我的项目中使用Linq和Lambda Operations，我需要根据类的两个属性对List进行排序。 因此，我使用了OrderBy（）。ThenBy（）方法如下：

class ValueWithIndex{ public long Value; public int Index; } ... List valuesWithIndex = new List(); for (int i = 0; i  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 ² ）最差情况。 当然，您添加的键越多，比较两个对象将花费更多时间，但排序操作的复杂性不会改变。