---
title: "Элементарные сортировки (выбором, пузырьком, вставками)"
url: https://algopath.pro/ru/patterns/elementary-sort
language: ru
summary: "Сортировки выбором, пузырьком и вставками сравнивают соседей и меняют их местами. Все три стоят O(n в квадрате) на перемешанных данных."
updated: 2026-08-24
---

# Элементарные сортировки (выбором, пузырьком, вставками)

Сортировки выбором, пузырьком и вставками сравнивают соседей и меняют их местами. Все три стоят O(n в квадрате) на перемешанных данных.

## Элементарные сортировки (выбором, пузырьком, вставками): как это работает?

Все три держат отсортированную часть и неотсортированную. Каждый раунд переносит через границу один элемент.

Сортировка выбором ищет в неотсортированной части минимум. Она меняет его местами с нужной позицией.

Пузырёк сравнивает соседние пары и меняет их при нарушении порядка. Наибольшее значение уплывает в конец.

Вставки берут следующий элемент и двигают его влево. Движение прекращается, как только сосед меньше.

Знать стоит именно вставки. На почти отсортированных данных они почти ничего не делают.

Все три работают на месте с O(1) памяти. Вставки и пузырёк устойчивы, выбор нет.

- `[5 | 2, 4, 1]` Сортировка вставками. Отсортирован пока только первый элемент.
- `[2, 5 | 4, 1]` Двойка проходит мимо пятёрки. Два элемента упорядочены.
- `[2, 4, 5 | 1]` Четвёрка проходит мимо пятёрки и встаёт после двойки.
- `[1, 2, 4, 5]` Единица уезжает в самое начало. Это самый дорогой ход здесь.
- `3 раунда` Почти отсортированный вход стоит одного сравнения на элемент. Сдвигов не будет вовсе.

## Элементарные сортировки (выбором, пузырьком, вставками): когда применять?

- n маленькое (десятки или пара сотен)
- массив уже почти отсортирован
- сортировка на месте с O(1) дополнительной памяти
- учебный/собеседовательный вопрос о механике сортировки
- важна стабильность, а простота приемлема

## Элементарные сортировки (выбором, пузырьком, вставками): с чем путают?

- **Быстрая сортировка (merge / quick)** - Merge и quick делят массив и стоят n log n. Эти три ничего не делят.
- **Сортировка без сравнений (подсчётом / поразрядная)** - Сортировка подсчётом читает значения, а не сравнивает их. Для этого нужен небольшой диапазон ключей.
- **Сортировка с пользовательским компаратором** - Та страница про то, какой порядок вам нужен. Эта про то, как порядок получается.
- **Бинарная куча / очередь с приоритетом** - Сортировка выбором каждый раунд ищет минимум перебором. Куча отдаёт его за log n.

## Элементарные сортировки (выбором, пузырьком, вставками): сложность по времени и памяти

n примерно до 5000 нормально при O(n в квадрате). На почти отсортированных данных вставки дают O(n).

## Элементарные сортировки (выбором, пузырьком, вставками): разбор примера

### Сортировка вставками на связном списке

Дан односвязный список, его надо отсортировать вставками.

Перевязывать узлы можно. Копировать значения в массив нельзя.

Стройте второй, отсортированный список по одному узлу.

Для каждого узла идите по отсортированному списку с начала, пока следующее значение не станет больше. Там и вставляйте.

```javascript
function insertionSortList(head) {
    const dummy = new ListNode(0);
    let node = head;

    while (node) {
        const next = node.next;

        // walk from the front each time: the sorted part has no back links
        let prev = dummy;
        while (prev.next && prev.next.val < node.val) {
            prev = prev.next;
        }

        node.next = prev.next;
        prev.next = node;
        node = next;
    }

    return dummy.next;
}
```

## Элементарные сортировки (выбором, пузырьком, вставками): частые ошибки

- **По привычке берут пузырёк** Он делает больше всех работы при том же классе сложности. Вставки лучше по умолчанию.
- **Сортируют так большой вход** При n в 1e5 квадрат это 1e10 операций. Возьмите встроенную сортировку.
- **Ведут внутренний цикл до нулевого индекса** Вставки должны остановиться, когда левый сосед меньше. Дальнейший проход убивает их лучший случай.
- **Берут выбор там, где важны равные ключи** Дальний обмен может перекинуть равные ключи друг через друга. Вставки сохраняют их исходный порядок.

## Элементарные сортировки (выбором, пузырьком, вставками): задачи с собеседований

- **Отсортировать массив** Любой из трёх хватает при нескольких тысячах элементов.
- **Сортировка вставками на списке** Тот же цикл, но по узлам, а не по ячейкам.
- **Сортировка цветов** Значений всего три, поэтому один проход бьёт любую сортировку сравнением.
- **Почти отсортированный массив** Вставки линейны, когда каждый элемент близко к своему месту.
- **Проверка роста в шеренге** Сравните ряд с его же отсортированной копией.
- **Сортировка по чётности** Это разбиение, а не полная сортировка.
- **Первое пропущенное положительное** Циклическая сортировка ставит каждое значение на свой индекс.

## JavaScript

```javascript
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}
```

## Python

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
```

## PHP

```php
function insertionSort(array $arr): array {
    for ($i = 1; $i < count($arr); $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}
```