Сортировка методом выбора в Java - Вопросы

На каждом шаге алгоритм находит минимальный элемент в неотсортированной части массива и меняет его местами с первым элементом этой части. Затем процесс повторяется для оставшейся части (без уже отсортированных элементов). С каждым проходом внешнего цикла граница отсортированной части сдвигается вправо, а наименьшие значения одно за другим встают в начало массива. Алгоритм работает на месте (in-place) и не требует дополнительной памяти.

Временная сложность равна O(n²) в лучшем, среднем и худшем случаях. Внешний цикл выполняется n раз, а внутренний в среднем n/2 раз, и это число сравнений не зависит от входных данных. Поэтому даже на уже отсортированном массиве алгоритм выполнит полный набор сравнений — раннего выхода нет. По памяти сложность O(1), так как сортировка идёт на месте.

Сортировка выбором делает минимум обменов: за весь проход выполняется не более n−1 перестановок, то есть O(n) обменов — по одному за проход внешнего цикла. Это выгодно, когда сама операция обмена дорогая (например, перемещаются большие объекты), даже несмотря на O(n²) сравнений. Кроме того, алгоритм сортирует на месте и не требует дополнительной памяти.

В базовой реализации на массиве — нет, сортировка выбором неустойчива. Обмен минимального элемента с текущим может изменить относительный порядок равных значений. Если порядок одинаковых элементов важен, следует выбрать устойчивый алгоритм, например сортировку вставками или слиянием.

Обе имеют сложность O(n²) и делают одинаковое число сравнений, но различаются числом обменов. Пузырьковая на каждом сравнении меняет местами соседние элементы, поэтому обменов может быть до O(n²). Сортировка выбором за один проход находит минимум и делает лишь один обмен — всего O(n) перестановок, что заметно меньше.