# Шпаргалка по алгоритмам сортировки Короткое введение: это краткий конспект основных алгоритмов сортировки, их сложности и примеры реализации. Подходит для подготовки к экзаменам. ## Основные понятия - Устойчивость: сохраняет относительный порядок равных элементов. - Сложность по времени: лучшая, средняя, худшая случаи. - Пространство: дополнительная память, требуемая алгоритмом. - Плохие случаи: зависят от входных данных и выбора стратегии. ## Основные алгоритмы ### Сортировка вставками (Insertion sort) - Идеально подходит для небольших массивов или частично отсортированных данных. - Стабильная: да. - Сложность: Best O(n), Average/Worst O(n^2). ### Сортировка выбором (Selection sort) - Простая реализация, не требует дополнительной памяти. - Стабильность: нет. - Сложность: всегда O(n^2) по времени, O(1) по памяти. ### Сортировка пузырьком (Bubble sort) - Простая, обучающая. Подходит для образовательных целей, редко используется на практике. - Стабильная: да. - Сложность: Best O(n), Average/Worst O(n^2). ### Быстрая сортировка (Quicksort) - Разделение массива на части и рекурсивная обработка. - Стабильность: нет. - Сложность: Average O(n log n), Worst O(n^2) без защиты от плохих данных; Space O(log n) за счет стека рекурсий. ### Сортировка слиянием (Merge sort) - Разделение массива пополам и слияние отсортированных частей. - Стабильная: да. - Сложность: O(n log n) во всех случаях; Space O(n) дополнительной памяти. ## Пример реализации ### Сортировка вставками на Python ```python 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 ``` ## Сравнение сложностей | Алгоритм | Лучшее | Среднее | Худшее | Стабильность | Примечания | |-------------------------|--------|---------|---------|--------------|-------------------------------------| | Insertion sort | O(n) | O(n^2) | O(n^2) | Да | Эффективен на небольших данных | | Selection sort | O(n^2) | O(n^2) | O(n^2) | Нет | Прост в реализации | | Bubble sort | O(n) | O(n^2) | O(n^2) | Да | Медленно на больших данных | | Quick sort | O(n log n) | O(n log n) | O(n^2) | Нет | Быстрая в среднем, риск худшего случая | | Merge sort | O(n log n) | O(n log n) | O(n log n) | Да | Требует дополнительной памяти | ## Примеры применения - Небольшие массивы, где важна простота реализации. - Месяцы, когда данные почти отсортированы (insert sort часто быстрее). - В качестве части других алгоритмов (например, как стадия в гибридных сортировках). ## Рекомендации - Выбирайте алгоритм в зависимости от размера данных и требований к устойчивости. - Для больших массивов чаще используют Quick sort (с защитой от худших кейсов) или Merge sort. - Поймите практические характеристики на своих реальных данных. ## Полезные ссылки - https://ru.wikipedia.org/wiki/Сортировка - https://en.wikipedia.org/wiki/Sorting_algorithm Если хочешь, могу адаптировать текст под конкретный курс или язык программирования.