Сортировка и поиск¶
Справочник по классификации, основным алгоритмам сортировки и методам поиска с примерами кода на Python.
1. Классификация алгоритмов сортировки¶
- Внутренняя — все данные помещаются в ОЗУ.
- Внешняя — данные на диске, не помещаются в память (сортировка слиянием больших файлов).
По механизму сравнения: сортировки сравнением (пузырёк, выбор, вставки, быстрая, слиянием, пирамидальная) и без сравнения (подсчётом, поразрядная, блочная).
2. Характеристики алгоритмов сортировки¶
- Временная сложность — число операций (лучший/средний/худший случай).
- Пространственная сложность — доп. память (in-place = O(1)).
- Адаптивность — ускоряется ли на частично отсортированных данных.
- Устойчивость (stability) — сохраняется ли порядок равных элементов.
3. Сортировка простым выбором (Selection sort)¶
Находим минимум в неотсортированной части, ставим его в начало.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
Сложность: O(n²) всегда. Память O(1). Не адаптивна, неустойчива. Плюс: минимум перестановок. Минус: медленная.
4. Сортировка простыми вставками (Insertion sort)¶
Берём элемент и вставляем в правильное место отсортированной части.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Сложность: O(n²) средн./худш., O(n) на почти отсортированных. Память O(1). Адаптивна, устойчива. Плюс: эффективна на малых/почти упорядоченных данных. Минус: медленная на больших.
5. Сортировка пузырьком (Bubble sort)¶
Соседние элементы сравниваются и меняются местами, «всплывая» к концу.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # уже отсортирован
break
return arr
Сложность: O(n²), O(n) с флагом на отсортированных. Память O(1). Адаптивна, устойчива. Плюс: простота. Минус: очень медленная.
6. Быстрая сортировка (Quicksort)¶
Выбираем опорный элемент (pivot), разбиваем массив на меньшие и большие, рекурсивно сортируем части.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + mid + quicksort(right)
Сложность: O(n log n) в среднем, O(n²) в худшем (неудачный pivot). Память O(log n) на стек. Обычно неустойчива. Плюс: быстрая на практике, in-place. Минус: худший случай, неустойчивость.
7. Классификация алгоритмов поиска¶
По типу данных/структуре: поиск в массиве/списке, в дереве, в хеш-таблице, в графе. По механизму: линейный (последовательный перебор), бинарный (для отсортированных данных), хеш-поиск (по ключу O(1)), обходы графов/деревьев (BFS/DFS).
8. Линейный поиск — первое вхождение / true-false¶
Перебираем элементы по порядку.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # индекс первого вхождения
return -1
def contains(arr, target):
for x in arr:
if x == target:
return True
return False
Сложность: O(n). Не требует сортировки, работает на любой структуре.
9. Линейный поиск — все вхождения / количество¶
def find_all(arr, target):
return [i for i, x in enumerate(arr) if x == target]
def count_occurrences(arr, target):
count = 0
for x in arr:
if x == target:
count += 1
return count
Сложность: O(n).
10. Бинарный поиск — первое вхождение / true-false¶
Работает только на отсортированном массиве: делим пополам, отбрасываем половину.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
def binary_contains(arr, target):
return binary_search(arr, target) != -1
Сложность: O(log n). Требует отсортированных данных.