Что такое временная сложность .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), , как упоминалось в Википедии , «Быстрая сортировка на практике часто быстрее, чем другие алгоритмы O (n log n)»

Answer 3

Добавление некоторой информации из недавнего добавления в MSDN по этой теме, для платформы 4.5, метод List.Sort использует другую стратегию сортировки в зависимости от количества элементов и разделов.

В этом методе используется метод Array.Sort, который применяет интроспективную сортировку следующим образом:

• Если размер раздела меньше 16 элементов, он использует алгоритм сортировки вставкой,
• Если число разделов превышает 2 * LogN, где N - диапазон входного массива, он использует алгоритм Heapsort.
• В противном случае он использует алгоритм быстрой сортировки.

Эта реализация выполняет нестабильную сортировку;то есть, если два элемента равны, их порядок может не сохраниться.Напротив, стабильная сортировка сохраняет порядок элементов, которые равны.

В среднем этот метод является операцией O (n log n), где n - это Count;в худшем случае это операция O (n ^ 2).

Answer 4

лучше всего это может быть асимптотически O (nlogn)