Существует множество различных алгоритмов сортировки, которые можно классифицировать по различным критериям, таким как сложность, стабильность, использование памяти и способ реализации. Вот основные виды сортировки:
1. Простые алгоритмы сортировки:
- Сортировка пузырьком (Bubble Sort): Повторяющиеся проходы по массиву, при каждом проходе сравниваются соседние элементы и меняются местами, если стоят в неправильном порядке.
- Сортировка вставками (Insertion Sort): Элементы вставляются на правильное место в уже отсортированной части массива.
- Сортировка выбором (Selection Sort): На каждой итерации выбирается минимальный (или максимальный) элемент из неотсортированной части массива и меняется местами с первым элементом этой части.
2. Быстрые алгоритмы сортировки:
- Быстрая сортировка (Quick Sort): Использует стратегию "разделяй и властвуй". Массив делится на две части с опорным элементом, после чего каждая часть сортируется рекурсивно.
- Сортировка слиянием (Merge Sort): Также использует стратегию "разделяй и властвуй". Массив делится пополам до тех пор, пока не останутся отдельные элементы, а затем они сливаются в отсортированные подмассивы.
- Пирамидальная сортировка (Heapsort): Строится двоичная куча (heap), после чего элементы извлекаются из кучи по одному и помещаются в отсортированный массив.
3. Алгоритмы с линейной сложностью (в некоторых случаях):
- Поразрядная сортировка (Radix Sort): Элементы сортируются по каждой цифре или разряду, начиная с младшего.
- Сортировка подсчётом (Counting Sort): Эффективна для сортировки чисел в ограниченном диапазоне. Сначала подсчитывается, сколько раз встречается каждый элемент, а затем создаётся отсортированный массив.
- Блочная сортировка (Bucket Sort): Делит элементы на "корзины" (buckets), сортирует их отдельно (возможно с использованием другого алгоритма) и затем объединяет.
4. Алгоритмы внешней сортировки (для больших данных, которые не помещаются в оперативную память):
- Сортировка слиянием на внешних носителях: Используется для сортировки файлов, которые слишком велики для оперативной памяти. Файл делится на части, каждая сортируется отдельно и затем происходит слияние отсортированных частей.
5. Параллельные алгоритмы сортировки:
- Параллельная быстрая сортировка (Parallel Quick Sort): Распараллеливает выполнение алгоритма быстрой сортировки.
- Параллельная сортировка слиянием (Parallel Merge Sort): Распараллеливает выполнение сортировки слиянием, ускоряя процесс на многопоточных системах.
6. Стабильные и нестабильные сортировки:
- Стабильная сортировка: Алгоритм считается стабильным, если он сохраняет относительный порядок элементов с одинаковыми ключами (например, сортировка слиянием, сортировка вставками).
- Нестабильная сортировка: Относительный порядок одинаковых элементов может измениться (например, быстрая сортировка, пирамидальная сортировка).
7. Интерактивные и неинтерактивные сортировки:
- Интерактивная сортировка: Сортировка, которая может динамически изменять порядок элементов в зависимости от добавления новых данных (например, дерево поиска).
- Неинтерактивная сортировка: Алгоритмы, которые работают с фиксированным набором данных (например, сортировка пузырьком или быстрая сортировка).
8. Натуральные сортировки:
- Натуральная сортировка (Natural Sort): Сортировка, которая учитывает числовое значение строк (например, "file10" будет следовать за "file2", а не за "file1").
Каждый из этих алгоритмов имеет свои преимущества и недостатки, и выбор алгоритма зависит от конкретной задачи, объёма данных и требований к производительности.
Вместо оглавления. Что вы найдете на канале QA Helper - справочник тестировщика?
Не забудьте подписаться на канал, чтобы не пропустить полезную информацию: QA Helper - справочник тестировщика
Пишите в комментариях какой пункт было бы интересно рассмотреть более подробно.
Обязательно прочитайте: Что должен знать и уметь тестировщик
Также будет интересно почитать: Вопросы которые задают на собеседовании тестировщикам
