Сортировка выбором

Находим следующий минимум

Сортировка выбором делит массив на две части: слева уже находится готовый отсортированный префикс, а справа остаются элементы, из которых нужно выбрать следующий. На каждом шаге алгоритм ищет минимальный элемент справа и ставит его в начало этой части.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        int tmp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = tmp;
    }
}

После первой итерации в a[0] лежит минимум всего массива. После второй — два минимальных элемента уже стоят в правильном порядке, и так далее. Важно, что поиск минимума не меняет массив: обмен выполняется только один раз в конце каждой внешней итерации.

Чем она отличается от пузырьковой

Пузырьковая сортировка может делать много обменов за один проход, а сортировка выбором — не больше одного. Зато число сравнений почти не зависит от исходного порядка: даже если массив уже отсортирован, алгоритм всё равно просматривает оставшуюся часть в поисках минимума.

Сложность

Количество сравнений остаётся O(n²) в лучшем, среднем и худшем случаях. Дополнительная память — O(1). Сильная сторона алгоритма — небольшое число обменов, но по времени на больших массивах он всё равно проигрывает более эффективным сортировкам.