Назад к вопросам
Junior
107
questionbank
Какие алгоритмы сортировки ты знаешь?
Sobes Copilot
Получайте ответы в реальном времени
Ответ от нейросети
sobes.tech AI
- Сортировка выбором (Selection Sort): Находит минимальный элемент из несортированной части массива и помещает его в начало.
- Сортировка вставками (Insertion Sort): Постепенно строит отсортированный массив, вставляя каждый элемент из несортированной части на свое место.
- Пузырьковая сортировка (Bubble Sort): Многократно обходит массив, сравнивая соседние элементы и меняя их местами, если они расположены в неправильном порядке.
- Сортировка слиянием (Merge Sort): Рекурсивно делит массив на две половины, сортирует каждую половину, а затем объединяет (сливает) отсортированные половины.
- Быстрая сортировка (Quick Sort): Выбирает опорный элемент (pivot) и разбивает другие элементы на две подмассива: те, что меньше опорного, и те, что больше. Затем рекурсивно сортирует эти подмассива.
- Сортировка кучей (Heap Sort): Использует структуру данных "куча" (heap). Строит из массива максимальную кучу, а затем многократно извлекает из кучи максимальный элемент и помещает его в конец отсортированной части массива.
- Сортировка Шелла (Shell Sort): Улучшение сортировки вставками. Сортирует элементы, разделенные определенным интервалом, затем уменьшает интервал и повторяет процесс.
- Сортировка подсчетом (Counting Sort): Используется для сортировки целочисленных данных в определенном диапазоне. Считает количество вхождений каждого элемента и использует эту информацию для построения отсортированного массива.
- Поразрядная сортировка (Radix Sort): Сортирует числа, обрабатывая их по разрядам (единицы, десятки, сотни и т.д.), используя вспомогательный алгоритм сортировки (например, сортировка подсчетом).
Основные характеристики некоторых сортировок:
| Алгоритм Сортировки | Средняя сложность | Сложность в худшем случае | Пространственная сложность | Стабильный | В месте (In-place) |
|---|---|---|---|---|---|
| Выбором | O(n²) | O(n²) | O(1) | Нет | Да |
| Вставками | O(n²) | O(n²) | O(1) | Да | Да |
| Пузырьковая | O(n²) | O(n²) | O(1) | Да | Да |
| Слиянием | O(n log n) | O(n log n) | O(n) | Да | Нет |
| Быстрая | O(n log n) | O(n²) | O(log n) (для рекурсии) | Нет | Да (зависит от реализации) |
| Кучей | O(n log n) | O(n log n) | O(1) | Нет | Да |
| Шелла | Зависит от шагов | Зависит от шагов | O(1) | Нет | Да |
| Подсчетом | O(n + k) | O(n + k) | O(k) | Да | Нет |
| Поразрядная | O(nk) | O(nk) | O(n + k) | Да | Нет |
где n — размер массива, k — диапазон значений (для Counting Sort) или количество цифр (для Radix Sort).