Сортировка методом выбора в Java

Author: Tatyana Milkina

Еще один вариант сортировки - это сортировка выбором (Selection sort).

Идея алгоритма: ищем минимальный элемент в массиве и меняем его местами с элементом, находящимся в позиции ноль. Далее ищем следующий по величине элемент и меняем его с элементом с индексом 1 и так далее:

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

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

public class SelectionSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {    // i - номер текущего шага
            int pos = i;
            int min = array[i];
            // цикл выбора наименьшего элемента
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    pos = j;    // pos - индекс наименьшего элемента
                    min = array[j];
                }
            }
            array[pos] = array[i];
            array[i] = min;    // меняем местами наименьший с array[i]
        }
    }
}
import java.util.Arrays;

public class SelectionSorterExample {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            SelectionSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}
Читайте также:
Комментарии