🦀 Rust

Rust中的排序算法：详细指南

课程 29 / 35 • 完整阅读理论

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы — библиотекарь, и у вас есть огромная стопка книг, которые нужно расставить на полки по алфавиту. Если книг всего пять, вы сделаете это за пару минут. Но что, если книг миллион? Вы не сможете просто «посмотреть» и расставить — вам понадобится чёткий, пошаговый план действий. Этот план и есть алгоритм сортировки.

В программировании сортировка — это процесс упорядочивания данных по определённому правилу: от меньшего к большему, по алфавиту, по дате или по любому другому признаку. Зачем это нужно? Практически везде:

Поиск работает в сотни раз быстрее на отсортированных данных (вспомните, как вы ищете слово в словаре — вы не читаете все страницы подряд).
Базы данных сортируют записи перед выдачей пользователю.
Игры сортируют таблицы рекордов.
Любой список покупок, контактов или файлов — это результат сортировки.

Важно: Сортировка — это не просто «сделать красиво». Это фундамент, на котором строятся поиск, анализ данных и оптимизация. Без неё современные приложения работали бы в тысячи раз медленнее.

Представьте, что вы сортируете колоду карт. Можно перебирать карты одну за другой и вставлять каждую в нужное место (это один алгоритм). А можно разделить колоду пополам, отсортировать каждую половину отдельно, а потом объединить (это совсем другой алгоритм). Разные алгоритмы подходят для разных ситуаций: одни быстрее на маленьких объёмах, другие — на огромных, одни экономят память, другие — время.

В этой статье мы разберём пять классических алгоритмов на языке Rust. Вы не просто увидите код, а поймёте, как каждый алгоритм «думает» и почему он работает именно так.

Теория: как это работает изнутри

Прежде чем писать код, давайте разберёмся в механике. У каждого алгоритма есть две главные характеристики:

Сложность по времени (Big O) — сколько операций нужно выполнить. Например, O(n²) означает, что при увеличении количества элементов в 10 раз, время выполнения вырастет в 100 раз.
Сложность по памяти — сколько дополнительной памяти требуется. Некоторые алгоритмы сортируют «на месте» (in-place), не создавая новых массивов.

Рассмотрим пять алгоритмов, которые мы реализуем:

1. Сортировка пузырьком (Bubble Sort)

Самый простой для понимания, но самый медленный. Представьте, что вы проходите вдоль ряда чисел и каждый раз, когда видите пару, где левое больше правого, вы меняете их местами. После одного прохода самое большое число «всплывает» в конец, как пузырёк в газировке. Повторяем, пока все числа не встанут на свои места.

Сложность: O(n²) — для 1000 элементов нужно около 500 000 операций. Работает только на очень маленьких наборах данных.

2. Сортировка вставками (Insertion Sort)

Представьте, что вы сортируете карты в руке. Вы берёте новую карту и вставляете её в уже отсортированную часть. Алгоритм проходит по массиву слева направо, и каждый новый элемент «встраивается» в правильное место среди уже обработанных.

Сложность: O(n²) в худшем случае, но на почти отсортированных данных работает почти как O(n). Очень эффективен для маленьких массивов.

3. Сортировка выбором (Selection Sort)

Алгоритм ищет самый маленький элемент и ставит его в начало. Затем ищет второй по величине и ставит на второе место. И так далее. Просто, но неэффективно: каждый раз приходится просматривать весь оставшийся массив.

Сложность: O(n²) — всегда, независимо от данных. Памяти не требует дополнительной.

4. Быстрая сортировка (Quick Sort)

Самый популярный алгоритм. Выбирается «опорный» элемент (pivot). Все элементы меньше опорного перемещаются влево, больше — вправо. Затем процесс повторяется для левой и правой частей рекурсивно. Это как разделить класс на две группы: тех, кто ниже среднего роста, и тех, кто выше, а потом повторить внутри каждой группы.

Сложность: O(n log n) в среднем, O(n²) в худшем (но на практике это редкость). Очень быстрый.

5. Сортировка слиянием (Merge Sort)

Работает по принципу «разделяй и властвуй». Массив делится пополам, каждая половина сортируется отдельно, а затем два отсортированных массива сливаются в один. Представьте, что у вас две отсортированные стопки бумаг — вы просто сравниваете верхние листы и берёте меньший.

Сложность: O(n log n) всегда. Требует дополнительной памяти O(n).

Алгоритм	Лучший случай	Средний случай	Худший случай	Память
Пузырёк	O(n)	O(n²)	O(n²)	O(1)
Вставками	O(n)	O(n²)	O(n²)	O(1)
Выбором	O(n²)	O(n²)	O(n²)	O(1)
Быстрая	O(n log n)	O(n log n)	O(n²)	O(log n)
Слиянием	O(n log n)	O(n log n)	O(n log n)	O(n)

Синтаксис в Rust: все формы и варианты

Rust — язык, который заставляет вас думать о памяти. Это одновременно и сложность, и преимущество. Для сортировки у Rust есть встроенные методы, но мы будем писать свои, чтобы понять механику.

Основные понятия, которые нам понадобятся:

Vec<T> — динамический массив (как list в Python).
&mut [T] — изменяемый срез массива. Сортировка «на месте» работает именно со срезами.
swap — метод для обмена двух элементов местами.
Рекурсия — функция вызывает саму себя (нужна для быстрой сортировки и слиянием).

В Rust есть встроенная сортировка через .sort() и .sort_unstable(). Первая гарантирует стабильность (равные элементы сохраняют порядок), вторая — быстрее, но нестабильна. Мы не будем их использовать в примерах, но вы должны знать, что в реальном коде пишут именно так:

// Встроенная сортировка в Rust (используется в реальных проектах)
let mut numbers = vec![5, 3, 8, 1, 9, 2];
numbers.sort(); // Стабильная сортировка
println!("{:?}", numbers); // [1, 2, 3, 5, 8, 9]

// Нестабильная — быстрее, но не гарантирует порядок равных элементов
let mut items = vec![3, 1, 2, 3, 1];
items.sort_unstable();
println!("{:?}", items); // [1, 1, 2, 3, 3]

Важно: Встроенная сортировка Rust использует алгоритм Timsort (гибрид сортировки вставками и слиянием). Она очень быстрая и оптимизированная. Но для обучения мы напишем свои версии.

Примеры кода — от простого к сложному

Все примеры ниже — полностью рабочие. Вы можете скопировать их в файл main.rs и запустить через cargo run. Каждый пример содержит подробные комментарии на русском языке.

Пример 1: Сортировка пузырьком (Bubble Sort)

// Пример 1: Сортировка пузырьком
// Идея: проходим по массиву, меняем соседние элементы, если они в неправильном порядке.
// Самый большой элемент "всплывает" в конец после каждого прохода.

fn bubble_sort(arr: &mut [i32]) {
    // Получаем длину массива
    let n = arr.len();
    
    // Внешний цикл: каждый проход гарантирует, что один элемент встаёт на место
    for i in 0..n {
        // Флаг: были ли обмены на этом проходе?
        let mut swapped = false;
        
        // Внутренний цикл: сравниваем пары (n - i - 1, потому что конец уже отсортирован)
        for j in 0..n - i - 1 {
            // Если левый элемент больше правого — меняем местами
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1); // Встроенный метод Rust для обмена
                swapped = true; // Запоминаем, что был обмен
            }
        }
        
        // Если не было ни одного обмена — массив уже отсортирован, выходим
        if !swapped {
            break;
        }
    }
}

fn main() {
    let mut numbers = vec![64, 34, 25, 12, 22, 11, 90];
    println!("До сортировки: {:?}", numbers);
    
    bubble_sort(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Внешний цикл for i in 0..n выполняется n раз, но на практике мы выходим раньше через break, если массив уже отсортирован. Внутренний цикл сравнивает каждую пару. arr.swap(j, j + 1) — это встроенный метод Rust, который меняет элементы местами. Флаг swapped — оптимизация: если на проходе не было обменов, значит всё уже на своих местах.

Пример 2: Сортировка вставками (Insertion Sort)

// Пример 2: Сортировка вставками
// Идея: берём элемент из неотсортированной части и вставляем его в правильное место
// в уже отсортированной части (как карты в руке).

fn insertion_sort(arr: &mut [i32]) {
    let n = arr.len();
    
    // Начинаем со второго элемента (первый считаем уже отсортированным)
    for i in 1..n {
        // Запоминаем текущий элемент, который будем вставлять
        let key = arr[i];
        // j — индекс, куда будем вставлять (начинаем с предыдущего элемента)
        let mut j = i;
        
        // Сдвигаем элементы вправо, пока не найдём место для key
        // Используем while, потому что j может стать 0
        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1]; // Сдвигаем элемент вправо
            j -= 1; // Двигаемся влево
        }
        
        // Вставляем key на найденное место
        arr[j] = key;
    }
}

fn main() {
    let mut numbers = vec![12, 11, 13, 5, 6, 7];
    println!("До сортировки: {:?}", numbers);
    
    insertion_sort(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Мы начинаем с индекса 1, потому что первый элемент (индекс 0) уже образует отсортированную часть из одного элемента. key — это элемент, который мы вставляем. Внутренний цикл while сдвигает все элементы, которые больше key, на одну позицию вправо. Когда находим правильное место, вставляем key. Обратите внимание на условие j > 0 — это защита от выхода за границы массива.

Пример 3: Сортировка выбором (Selection Sort)

// Пример 3: Сортировка выбором
// Идея: находим минимальный элемент в неотсортированной части и ставим его в начало.

fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    
    // Внешний цикл: каждый раз устанавливаем один элемент на своё место
    for i in 0..n {
        // Предполагаем, что минимальный элемент находится на позиции i
        let mut min_idx = i;
        
        // Ищем реальный минимальный элемент в оставшейся части массива
        for j in (i + 1)..n {
            if arr[j] < arr[min_idx] {
                min_idx = j; // Нашли новый минимум
            }
        }
        
        // Если нашли элемент меньше, чем на позиции i — меняем местами
        if min_idx != i {
            arr.swap(i, min_idx);
        }
    }
}

fn main() {
    let mut numbers = vec![29, 10, 14, 37, 13, 33, 48];
    println!("До сортировки: {:?}", numbers);
    
    selection_sort(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Внешний цикл for i in 0..n фиксирует позицию, куда мы поставим очередной минимальный элемент. Внутренний цикл for j in (i + 1)..n ищет минимальный элемент в оставшейся части. Если min_idx не равен i, значит мы нашли элемент меньше текущего — меняем их местами. Обратите внимание: мы не используем дополнительный массив, всё делается «на месте».

Пример 4: Быстрая сортировка (Quick Sort) — версия с последним элементом как опорным

// Пример 4: Быстрая сортировка (Quick Sort)
// Идея: выбираем опорный элемент, разделяем массив на две части,
// рекурсивно сортируем каждую часть.

fn quick_sort(arr: &mut [i32]) {
    // Базовый случай: если в срезе 0 или 1 элемент — он уже отсортирован
    if arr.len() <= 1 {
        return;
    }
    
    // Выбираем опорный элемент (pivot) — последний элемент среза
    let pivot_index = arr.len() - 1;
    let pivot = arr[pivot_index];
    
    // Индекс для разделения: все элементы слева от него меньше pivot
    let mut i = 0;
    
    // Проходим по всем элементам, кроме последнего (он — pivot)
    for j in 0..pivot_index {
        // Если текущий элемент меньше или равен pivot — перемещаем его в левую часть
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1; // Расширяем левую часть
        }
    }
    
    // Ставим pivot на своё место (между левой и правой частями)
    arr.swap(i, pivot_index);
    
    // Рекурсивно сортируем левую часть (элементы меньше pivot)
    quick_sort(&mut arr[0..i]);
    
    // Рекурсивно сортируем правую часть (элементы больше pivot)
    quick_sort(&mut arr[i + 1..]);
}

fn main() {
    let mut numbers = vec![10, 80, 30, 90, 40, 50, 70];
    println!("До сортировки: {:?}", numbers);
    
    quick_sort(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Это классическая реализация Хоара. Мы выбираем последний элемент как опорный. Переменная i — это граница между элементами, меньшими pivot, и остальными. Цикл for j in 0..pivot_index проходит по всем элементам, кроме pivot. Если элемент меньше или равен pivot, мы меняем его с элементом на позиции i и увеличиваем i. После цикла ставим pivot на позицию i — теперь слева от него все меньшие, справа — все большие. Затем рекурсивно вызываем quick_sort для левой и правой частей. Обратите внимание на синтаксис &mut arr[0..i] — это изменяемый срез, Rust позволяет передавать часть массива.

Пример 5: Быстрая сортировка с рандомизированным выбором опорного элемента

// Пример 5: Быстрая сортировка с рандомизированным pivot
// Улучшение: выбираем случайный опорный элемент, чтобы избежать худшего случая O(n²)
// на уже отсортированных данных.

use rand::Rng; // Подключаем генератор случайных чисел

fn quick_sort_random(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    
    // Генерируем случайный индекс для pivot
    let mut rng = rand::thread_rng();
    let random_index = rng.gen_range(0..arr.len());
    
    // Меняем случайный элемент с последним, чтобы использовать тот же алгоритм разделения
    arr.swap(random_index, arr.len() - 1);
    
    let pivot_index = arr.len() - 1;
    let pivot = arr[pivot_index];
    let mut i = 0;
    
    for j in 0..pivot_index {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    
    arr.swap(i, pivot_index);
    
    quick_sort_random(&mut arr[0..i]);
    quick_sort_random(&mut arr[i + 1..]);
}

fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5, 6, 7]; // Уже отсортированный массив — худший случай для обычной быстрой сортировки
    println!("До сортировки: {:?}", numbers);
    
    quick_sort_random(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Отличие от предыдущего примера — мы выбираем случайный индекс random_index и меняем его с последним элементом. Это гарантирует, что даже на отсортированных данных мы не попадём в худший случай O(n²). Для работы с rand нужно добавить зависимость в Cargo.toml: rand = "0.8". Этот пример показывает, как маленькое изменение может кардинально улучшить производительность.

Пример 6: Сортировка слиянием (Merge Sort)

// Пример 6: Сортировка слиянием (Merge Sort)
// Идея: делим массив пополам, рекурсивно сортируем каждую половину,
// затем сливаем две отсортированные половины в одну.

fn merge_sort(arr: &mut [i32]) {
    // Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if arr.len() <= 1 {
        return;
    }
    
    // Находим середину массива
    let mid = arr.len() / 2;
    
    // Создаём изменяемые срезы для левой и правой половин
    // split_at_mut — безопасный способ разделить массив на две части
    let (left, right) = arr.split_at_mut(mid);
    
    // Рекурсивно сортируем каждую половину
    merge_sort(left);
    merge_sort(right);
    
    // Сливаем отсортированные половины обратно в arr
    // Для этого нам нужен временный буфер
    let mut temp = Vec::with_capacity(arr.len());
    
    // Указатели для левой и правой половин
    let mut i = 0; // Индекс в левой половине
    let mut j = 0; // Индекс в правой половине
    
    // Сливаем, пока есть элементы в обеих половинах
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            temp.push(left[i]);
            i += 1;
        } else {
            temp.push(right[j]);
            j += 1;
        }
    }
    
    // Добавляем оставшиеся элементы из левой половины (если есть)
    while i < left.len() {
        temp.push(left[i]);
        i += 1;
    }
    
    // Добавляем оставшиеся элементы из правой половины (если есть)
    while j < right.len() {
        temp.push(right[j]);
        j += 1;
    }
    
    // Копируем отсортированные элементы обратно в исходный массив
    for (idx, value) in temp.iter().enumerate() {
        arr[idx] = *value;
    }
}

fn main() {
    let mut numbers = vec![38, 27, 43, 3, 9, 82, 10];
    println!("До сортировки: {:?}", numbers);
    
    merge_sort(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: split_at_mut(mid) — это безопасный способ разделить изменяемый массив на две части. Мы рекурсивно сортируем каждую половину. Затем создаём временный вектор temp и сливаем две половины: сравниваем первые элементы, меньший добавляем в temp. Когда одна половина заканчивается, просто копируем оставшиеся элементы из другой. В конце копируем temp обратно в arr. Этот алгоритм требует O(n) дополнительной памяти, но работает стабильно быстро — O(n log n) в любом случае.

Пример 7: Сортировка слиянием — итеративная версия (без рекурсии)

// Пример 7: Итеративная сортировка слиянием (Bottom-up Merge Sort)
// Идея: начинаем с массивов размера 1, сливаем их в массивы размера 2,
// затем 4, 8 и так далее, пока не получим один отсортированный массив.

fn merge_sort_iterative(arr: &mut [i32]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }
    
    // Внешний цикл: размер подмассива удваивается на каждом шаге
    let mut size = 1;
    while size < n {
        // Внутренний цикл: сливаем пары подмассивов
        let mut left = 0;
        while left < n {
            // Определяем границы для слияния
            let mid = (left + size).min(n);
            let right = (left + 2 * size).min(n);
            
            // Если есть что сливать (есть правая часть)
            if mid < right {
                // Сливаем arr[left..mid] и arr[mid..right]
                merge_in_place(arr, left, mid, right);
            }
            
            left += 2 * size; // Переходим к следующей паре
        }
        size *= 2; // Удваиваем размер подмассива
    }
}

// Вспомогательная функция для слияния двух отсортированных частей
fn merge_in_place(arr: &mut [i32], left: usize, mid: usize, right: usize) {
    // Создаём временный вектор для результата слияния
    let mut temp = Vec::with_capacity(right - left);
    
    let mut i = left;  // Индекс для левой части
    let mut j = mid;   // Индекс для правой части
    
    // Сливаем, пока есть элементы в обеих частях
    while i < mid && j < right {
        if arr[i] <= arr[j] {
            temp.push(arr[i]);
            i += 1;
        } else {
            temp.push(arr[j]);
            j += 1;
        }
    }
    
    // Добавляем оставшиеся элементы из левой части
    while i < mid {
        temp.push(arr[i]);
        i += 1;
    }
    
    // Добавляем оставшиеся элементы из правой части
    while j < right {
        temp.push(arr[j]);
        j += 1;
    }
    
    // Копируем отсортированные элементы обратно в исходный массив
    for (idx, value) in temp.iter().enumerate() {
        arr[left + idx] = *value;
    }
}

fn main() {
    let mut numbers = vec![38, 27, 43, 3, 9, 82, 10, 1, 5, 6];
    println!("До сортировки: {:?}", numbers);
    
    merge_sort_iterative(&mut numbers);
    
    println!("После сортировки: {:?}", numbers);
}

Объяснение: Это итеративная версия сортировки слиянием. Внешний цикл while size < n управляет размером подмассивов. Внутренний цикл while left < n проходит по массиву и сливает пары подмассивов размера size. Функция merge_in_place делает то же самое, что и в рекурсивной версии, но работает с индексами, а не со срезами. Преимущество итеративной версии — нет риска переполнения стека при рекурсии на очень больших массивах.

Сравнение с Python: чем похоже и чем отличается

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

Аспект	Python	Rust
Синтаксис	Лаконичный, меньше символов	Более многословный, но явный
Память	Автоматическое управление, сборщик мусора	Владение (ownership), заимствование (borrowing), никакого сборщика
Изменяемость	Списки изменяемы по умолчанию	Нужно явно указывать `&mut` для изменяемой ссылки
Срезы	`arr[:mid]` создаёт копию	`&mut arr[0..mid]` — это ссылка на часть массива, без копирования
Рекурсия	Глубина рекурсии ограничена (обычно 1000)	Глубина рекурсии тоже ограничена, но можно использовать итеративные версии
Производительность	Медленнее из-за динамической типизации и интерпретации	Быстрее, компилируется в машинный код
Безопасность	Ошибки на этапе выполнения	Компилятор проверяет память и типы на этапе компиляции

Вот как выглядит быстрая сортировка на Python для сравнения:

# Python: быстрая сортировка (для сравнения)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

numbers = [10, 80, 30, 90, 40, 50, 70]
print(quick_sort(numbers))

Главное отличие: В Python мы создаём новые списки left и right на каждом шаге рекурсии. Это удобно, но требует много памяти. В Rust мы сортируем «на месте» (in-place), изменяя исходный массив через изменяемые ссылки. Rust заставляет вас думать о том, кто владеет данными и сколько памяти вы используете.

Совет: Если вы переходите с Python на Rust, забудьте про «просто создам новый список». В Rust эффективный код часто означает работу с существующими данными через ссылки и срезы.

Типичные ошибки и подводные камни

Даже опытные программисты допускают ошибки при реализации сортировки. Вот самые частые проблемы в Rust:

1. Выход за границы массива

Самая распространённая ошибка. Например, в сортировке вставками:

// ОШИБКА: выход за границы
while arr[j - 1] > key { // Если j = 0, то j - 1 вызовет panic
    arr[j] = arr[j - 1];
    j -= 1;
}

Решение: Всегда проверяйте границы: while j > 0 && arr[j - 1] > key. В Rust порядок важен — сначала проверка j > 0, потом доступ к массиву.

2. Забыли про изменяемость

Rust строг к изменяемости. Если вы передаёте массив в функцию, но не указываете &mut, компилятор выдаст ошибку:

← 上一课 Rust中的正则表达式：详细指南下一步 → Rust中的搜索算法：详细指南