什么是.NET List.sort()的时间复杂度

Question

什么是C#的时间复杂性 List<T>.Sort()

我想这是o(N)

但在我搜索了很多之后,我没有得到任何准确的结果.

Answer 1

http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

此方法使用Array.Sort,它使用QuickSort算法.此实现执行不稳定的排序; 也就是说,如果两个元素相等,则可能不会保留它们的顺序.相反,稳定的排序保留了相等元素的顺序.

平均而言,此方法是O(n log n)运算,其中n是Count; 在最坏的情况下,它是O(n ^ 2)操作.

Answer 2

从文档:

平均而言,此方法是O(n log n)运算,其中n是Count; 在最坏的情况下,它是O(n ^ 2)操作.

这是因为它使用Quicksort.虽然这通常是O(n log n),如维基百科上所述,"Quicksort在实践中通常比其他O(n log n)算法更快"

Answer 3

对于框架4.5，从MSDN的最新成员中添加了一些有关此主题的信息，对于框架4.5，List.Sort方法根据元素和分区的数量使用不同的排序策略。

此方法使用Array.Sort方法，该方法应用内省式排序，如下所示：

• 如果分区大小少于16个元素，则使用插入排序算法。
• 如果分区数超过2 * LogN（其中N是输入数组的范围），它将使用Heapsort算法。
• 否则，它将使用Quicksort算法。

此实现执行不稳定的排序；也就是说，如果两个元素相等，则可能不会保留其顺序。相反，稳定排序保留了元素相等的顺序。

平均而言，此方法是O（n log n）运算，其中n是Count；在最坏的情况下，它是O（n ^ 2）运算。