1. 首頁
  2. 問答
  3. 時間是什麼.NET List.sort（）

時間是什麼.NET List.sort（）

2012-03-08 67 views
10

是什麼時候的的List<T>.Sort()時間是什麼.NET List.sort（）

我想這是爲O C＃（N）的複雜性

但是我搜索了很多之後，我沒有得到任何的複雜性準確的結果。

來源

2012-03-08 Anders Lind

+0

您的意思是'List.Sort'，或'List .Sort'？ – 2012-03-08 02:37:27

+0

列表 .sort抱歉 – 2012-03-08 02:37:58

回答

19

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

此方法使用Array.Sort，它使用QuickSort算法。此實現執行不穩定的排序;也就是說，如果兩個元素相等，他們的順序可能不會被保留。相反，穩定的排序保留了相同元素的順序。

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

來源

2012-03-08 02:38:41 zerkms

5

從the documentation：

平均來說，此方法是一個爲O​​（n log n）的操作，其中n是計數;在最壞的情況下，它是一個O（n^2）操作。

這是因爲它使用Quicksort。雖然這是典型的爲O（n log n）的，as mentioned on Wikipedia 「快速排序通常更快的是在實踐中比其他爲O（n log n）的算法」

來源

2012-03-08 02:37:26

0

最好的也可以是漸進是O（nlogn）

來源

2012-03-08 02:37:32 Tom

2

添加從近期除了MSDN關於這一主題的一些信息，框架4.5，List.Sort方法取決於元素和分區的數量採用的是不同的排序策略。

該方法使用如下應用 內省排序Array.sort方法：

  • 如果分區大小是少於16個元素，它使用了一個插入 排序算法。
  • 如果分區數超過2 * LogN，其中N 是輸入數組的範圍，它使用Heapsort算法。
  • 否則，它使用Quicksort算法。

此實現執行 不穩定排序;也就是說，如果兩個元素相同，則它們的訂單 可能不會保留。相反，穩定的排序保留了相同元素的順序 。

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

來源

2016-06-27 04:52:18 Agalo

相關問題

 相關問題