Какие есть методы поиска, сортировки, вставки и удаления? Выбор структур данных

"Методы поиска включают линейный, бинарный, хеш-поиск, поиск в деревьях. Сортировки — пузырьковая, вставками, быстрая, слиянием, Timsort. Для вставки и удаления сложность зависит от структуры: list — O(1) в конец, O(n) в середину, dict/set — O(1) в среднем, deque — O(1) с концов, heapq — O(log n). Выбор структуры зависит от требуемых операций и их частоты."

---

Поиск (Search methods)

• Линейный поиск (linear search) — перебор элементов по очереди, O(n). Простой, но медленный для больших наборов данных.

• Бинарный поиск (binary search) — работает только в отсортированных структурах, O(log n). Разделяем массив пополам и ищем в нужной части.

• Хеш-поиск — через хеш-таблицы (dict, set в Python), в среднем O(1).

• Поиск по дереву — в сбалансированных деревьях поиска (AVL, Red-Black) O(log n).

---

Сортировка (Sorting)

• Пузырьковая (bubble sort) — учебная, O(n²), почти не используется в реальности.

• Сортировка вставками (insertion sort) — O(n²), эффективна для почти отсортированных данных.

• Быстрая сортировка (quick sort) — O(n log n) в среднем, O(n²) в худшем. Python Timsort частично на ней основан.

• Сортировка слиянием (merge sort) — O(n log n), стабильная, требует доп. память.

• Timsort — алгоритм Python по умолчанию (sorted() и .sort()), адаптивный, стабильный, O(n log n).

---

Вставка (Insertion)

• В массив — O(1) в конец, O(n) в середину (так как сдвигаются элементы).

• В связный список — O(1), если есть ссылка на нужное место.

• В дерево — O(log n) в сбалансированных, O(n) в несбалансированных.

• В хеш-таблицу — в среднем O(1).

---

Удаление (Deletion)

• Из массива (list) — O(n) при удалении из середины.

• Из связного списка — O(1) при известном узле.

• Из дерева — O(log n) в сбалансированных.

• Из хеш-таблицы — O(1) в среднем.

---

Выбор структуры данных зависит от задачи:

• list — универсальный, быстрый доступ по индексу, но вставка/удаление в середине дорогие.

• dict / set — быстрый поиск и вставка, но без упорядоченности (в Python 3.7+ dict хранит порядок добавления).

• deque — оптимален для вставки/удаления с начала и конца.

• heapq — минимальная куча для приоритетов.

• OrderedDict — словарь с сохранением порядка (сейчас почти не нужен из-за Python 3.7+).