什么是.NET List.sort（）的时间复杂度
什么是C＃的List.Sort()时间复杂度List.Sort()
我想这是o（N）
但在我搜索了很多之后，我没有得到任何准确的结果。
http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx
此方法使用Array.Sort，它使用QuickSort算法。 此实现执行不稳定的排序; 也就是说，如果两个元素相等，则可能不会保留它们的顺序。 相反，稳定的排序保留了相等元素的顺序。
平均而言，此方法是O（n log n）运算，其中n是Count; 在最坏的情况下，它是O（n ^ 2）操作。
从文档 ：
平均而言，此方法是O（n log n）运算，其中n是Count; 在最坏的情况下，它是O（n ^ 2）操作。
这是因为它使用Quicksort。 虽然这通常是O（n log n）， 如维基百科上所述 ，“Quicksort在实践中通常比其他O（n log n）算法更快”
在最近添加到MSDN上的一些信息中，对于框架4.5，List.Sort方法使用不同的排序策略，具体取决于元素和分区的数量。
此方法使用Array.Sort方法，该方法应用内省排序，如下所示：
- 如果分区大小少于16个元素，则使用插入排序算法。
- 如果分区数超过2 * LogN，其中N是输入数组的范围，则它使用Heapsort算法。
- 否则，它使用Quicksort算法。
此实现执行不稳定的排序; 也就是说，如果两个元素相等，则可能不会保留它们的顺序。 相反，稳定的排序保留了相等元素的顺序。
平均而言，此方法是O（n log n）运算，其中n是Count; 在最坏的情况下，它是O（n ^ 2）操作。
最好的是渐近可以是O（nlogn）