tgoop.com/CScience1/3015
Last Update:
Алгоритмы сортировок
Самая частая тема, которую спрашивают на собеседованиях. Рассмотрим, какие есть и их сложность по времени. Подробно как они работают, по ссылкам в соответствующих постах.
1. Сортировка пузырьком
Худшее время - O(n^2) | Лучшее время - O(n)
2. Сортировка выбором
Лучшее время O(n^2) | В cреднем - O(n^2) | Худшее время - O(n^2)
3. Сортировка подсчётом
Сложность оценивается как O(n + k), где n — количество элементов, k — диапазон значений.
4. Поразрядная сортировка
В лучшем случаи: O(n) | В худшем: O(n*k)
5. Bucket sort
Наименьшая и средняя сложность (O(n))
6. Сортировка Шелла
В лучшем случаи: O(n) | В cреднем: O(n (logn)^2) | В худшем: O(n log^2n)
7. Tim Sort
В лучшем случаи: O(n) | В cреднем: O(n logn) | В худшем: O(n logn)
8. Блинная сортировка
Лучший случай: O(n) | Средний случай: O(n²) | Худший случай: O(n²)
9. Сортировка перемешиванием
Худшее время - O(n^2) | Лучшее время - O(n)
10. Gnome Sort
В лучшем: O(n) | В худшем: O(n^2)
11. Odd-Even Sort
В лучшем: O(n)В худшем: O(n^2)
12. Сортировка расческой
Худшее время - O(n^2) | Лучшее время - O(n log n)
13. Сортировка вставками
Худшее время - O(n^2) | Лучшее время - O(n) или O(1)
14. Голубиная сортировка
Время: O(n+range)
15. Циклическая сортировка
Время: O(n^2)
16. Нитевидная сортировка
В лучшем: O(n) | В худшем: O(n^2)
17. Битоническая сортировка
Время: O(log^2n)
18. Stooge Sort
Время: O(n^(log3/log1.5))
19. Бисерная сортировка
Время: O(n^2)
20. Топологическая сортировка
Время: O(V + E)
21. Быстрая сортировка
Худшее время - O(n^2) | Лучшее время - O(n log n)
22. Сортировка слиянием
Худшее время - O(n log n) | Лучшее время - O(n log n)
23. Пирамидальная сортировка
Худшее время - O(n log n) | Лучшее время - O(n log n) или O(n)
BY Computer Science
Share with your friend now:
tgoop.com/CScience1/3015