Сортировка выбором
Последнее обновление
Сортировка выбором делит массив на отсортированную область слева и неотсортированную справа. На каждом проходе она просматривает неотсортированную область, находит наименьший элемент и меняет его местами с первой неотсортированной позицией - увеличивая отсортированную область на один. Нажмите «воспроизвести» выше, чтобы наблюдать просмотр и обмен, или проходите по одному сравнению за раз.
Сортировка выбором всегда выполняет одинаковое число сравнений независимо от входных данных, но делает не более n-1 обменов - гораздо меньше, чем пузырьковая сортировка - что важно, когда запись обходится дорого.
Временная и пространственная сложность
| Случай | Сложность | Примечания |
|---|---|---|
| Лучший случай | O(n²) | Сравнения выполняются даже для отсортированного массива |
| Средний случай | O(n²) | Случайный порядок |
| Худший случай | O(n²) | Обратный порядок |
| Память | O(1) | На месте |
| Устойчивая | Нет | Обмены могут переставлять равные элементы |
Пошагово
| Шаг | Что происходит |
|---|---|
| 1 | Считаем весь массив неотсортированным. |
| 2 | Просматриваем неотсортированную область, чтобы найти минимальный элемент. |
| 3 | Меняем этот минимум местами с первой неотсортированной позицией. |
| 4 | Сдвигаем границу на один шаг вправо (эта позиция теперь отсортирована). |
| 5 | Повторяем, пока не останется один неотсортированный элемент. |
Разобранный пример
Сортировка [5, 2, 4, 1]:
| Проход | Массив | Действие |
|---|---|---|
| Начало | [5, 2, 4, 1] | Весь массив неотсортирован. |
| 1 | [1, 2, 4, 5] | Просматриваем [5, 2, 4, 1], минимум - 1 на индексе 3; меняем местами с индексом 0. |
| 2 | [1, 2, 4, 5] | Просматриваем [2, 4, 5], минимум - 2 уже на индексе 1; меняется сам с собой. |
| 3 | [1, 2, 4, 5] | Просматриваем [4, 5], минимум - 4 уже на индексе 2; перемещение не нужно. |
| Готово | [1, 2, 4, 5] | Остался только 5, значит он уже на своём месте. |
Когда использовать сортировку выбором
| Используйте, когда | Избегайте, когда |
|---|---|
Запись дорогая - выполняется не более n-1 обменов. | Массив большой - доминируют O(n²) сравнения. |
| Нужна простая, легко реализуемая сортировка на месте. | Нужна устойчивая сортировка, сохраняющая порядок равных ключей. |
Память ограничена - используется лишь O(1) дополнительной памяти. | Данные почти отсортированы - она не может завершиться раньше, как сортировка вставками. |
| Набор данных крошечный и важна предсказуемая производительность. | Важна пропускная способность - сортировки O(n log n), такие как быстрая сортировка, гораздо быстрее. |
Код Selection Sort
Чистая, готовая к запуску реализация Selection Sort на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Selection Sort на Python
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)Код Selection Sort на JavaScript
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));Код Selection Sort на Java
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Код Selection Sort на C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}Код Selection Sort на C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}Часто задаваемые вопросы о сортировке выбором
Какова временная сложность сортировки выбором?
Сортировка выбором имеет сложность
O(n²) во всех случаях - лучшем, среднем и худшем - потому что она всегда просматривает всю неотсортированную область, чтобы найти каждый минимум. Она использует O(1) дополнительной памяти.Устойчива ли сортировка выбором?
Стандартная версия на месте неустойчива, потому что обмен удалённого минимума на его позицию может передвинуть равный элемент вперёд другого. Устойчивый вариант существует, но требует сдвига вместо обмена.
Когда сортировка выбором полезна?
Она полезна, когда стоимость записи в память высока, поскольку она выполняет не более
n-1 обменов - минимально возможное число для сортировки сравнением, которая перемещает элементы.В чём разница между сортировкой выбором и пузырьковой сортировкой?
Обе являются сортировками сравнением со сложностью
O(n²), но сортировка выбором делает не более n-1 обменов, тогда как пузырьковая сортировка может делать до O(n²) обменов. Пузырьковая сортировка также может обнаружить уже отсортированный массив и остановиться раньше, тогда как сортировка выбором всегда выполняет все проходы.Что использовать: сортировку выбором или сортировку вставками?
В большинстве случаев предпочтительнее сортировка вставками - она устойчива, работает за
O(n) на почти отсортированных данных и в среднем быстрее. Выбирайте сортировку выбором только тогда, когда приоритетом является минимизация числа записей, так как она гарантирует не более n-1 обменов.Почему сортировка выбором всегда работает за O(n²), даже на отсортированном массиве?
Сортировка выбором не может узнать, что элемент уже является минимумом, не просмотрев остальную часть неотсортированной области, поэтому она выполняет все сравнения на каждом проходе независимо от порядка входных данных. Поэтому лучший случай равен худшему при
O(n²) - в отличие от сортировки вставками или пузырьковой, которые могут завершиться досрочно.Связанные ресурсы
Больше визуализаций
