Сортировка методом выбора в Java
Еще один вариант сортировки - это сортировка выбором (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));
}
}
}
Please log in or register to have a possibility to add comment.