Сортировка выбором :: Selection sort

Базовый алгоритм для сортировок выбором. Работает медленно, но некоторые её модификации (например, пирамидальная сортировка) могут показывать очень высокую эффективность.
Алгоритм
Проходим массив и находим в нём максимальный элемент. Найденый максимум меняем местами с последним элементом. Затем проходим по неотсортированной части массива (от первого элемента до предпоследнего) и находим в ней максимум, который затем меняем местами с предпоследним элементом масива. Продолжаем действия, пока не отсортируем полностью.
Если кроме максимумов конец массива таке перемещать минимальные элементы его начао, то мы пучаем двухстороннюю сортировку выбором.
Характеристики алгоритма
Название | Сортировка выбором (Selection sort) | |
---|---|---|
Другие названия | Сортировка выделением | |
Класс | Сортировки выбором | |
Устойчивость | Нет | |
Сравнения | Да | |
Сложность по времени | Худшая | O(n2 / 2) |
Средняя | O(n2 / 2) | |
Лучшая | O(n2 / 2) | |
Сложность по памяти | Общая | O(n) |
Дополнительная | O(1) |