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

Question

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

我猜是O(N)。

但是我搜索了很多，没有得到准确的结果。

- Anders Lind

---

你是指 List.Sort 还是 List<T>.Sort？ - John Saunders

Answer 1

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

该方法使用Array.Sort，采用了快速排序算法。此实现执行不稳定排序;也就是说，如果两个元素相等，则它们的顺序可能无法保留。相比之下，稳定排序可以保留相等元素的顺序。

平均情况下，该方法是一个O(n log n)的操作，其中n是Count；在最坏情况下，它是一个O(n ^ 2)的操作。

- zerkms

Answer 2

根据文档，这个方法的平均时间复杂度是O(n log n)，其中n是Count；在最坏情况下，它的时间复杂度是O(n ^ 2)。这是因为它使用了快速排序算法。虽然快速排序通常是O(n log n)，维基百科上提到，“实际上，快速排序比其他O(n log n)算法更快”。

- Reed Copsey

Answer 3

最近在MSDN上新增了一些关于4.5框架中List.Sort方法的信息，该方法会根据元素数量和分区情况使用不同的排序策略。

该方法使用Array.Sort方法应用内省排序算法，具体如下：

• 如果分区大小少于16个元素，则使用插入排序算法。
• 如果分区数超过输入数组范围N的2 * LogN，则使用堆排序算法。
• 否则，使用快速排序算法。

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

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

- Abhinav Galodha

---

我可以问一下分区大小是指什么吗？谢谢。 - Daniel B

Answer 4

在List.sort文档底部，您会看到使用的算法如下：

此方法使用Array.Sort方法，应用内省排序算法如下：

如果分区大小小于或等于16个元素，则使用插入排序算法。

如果分区数超过输入数组范围n的2log n，则使用堆排序算法。

否则，使用快速排序算法。

因此，快速排序是默认排序算法，但对于16个或更少元素的列表，将使用插入排序进行排序，并且如果快速排序算法需要超过2log n个枢轴，则改为使用堆排序。

这种情况很重要，因为它将最坏情况的渐近复杂度更改为O(n log n)（而不是常规快速排序的O(n^2)）。

这是因为每个枢轴操作期间执行的工作不超过O(n)，并且最多有O(log n)个枢轴操作，因此在使用堆排序之前，快速排序算法运行的时间不超过O(n log n)。

因此，整个排序算法的渐近时间复杂度受O(2n log n + n log n)的限制，这与O(n log n)相同。

如果您仍然不确定，请查看备注底部的时间复杂度：

此方法是一个O(n log n)操作，其中n为Count。

- maxcampman

Answer 5

最优的渐进时间复杂度是O(nlogn)

- Tom