Как отсортировать вектор в Rust: по возрастанию, по убыванию и с кастомной логикой

Основы сортировки в Rust

В Rust сортировка векторов реализована через методы трейта Slice. Все основные методы сортируют на месте (in-place), изменяя исходный вектор. Если нужна новая отсортированная копия, можно сначала клонировать вектор.

1. Простая сортировка по возрастанию: sort()

Метод sort() работает для типов, которые реализуют трейт Ord (полная упорядоченность). Числа, строки и многие стандартные типы его реализуют.

fn main() {
    let mut numbers = vec![5, 2, 8, 1, 9];
    numbers.sort();
    println!("{:?}", numbers); // [1, 2, 5, 8, 9]

    let mut words = vec!["banana", "apple", "cherry", "date"];
    words.sort();
    println!("{:?}", words); // ["apple", "banana", "cherry", "date"]
}

Важно: sort() использует стабильную сортировку (алгоритм merge sort), сохраняя относительный порядок равных элементов.

2. Сортировка по убыванию: sort_by() с reverse()

Самый простой способ — отсортировать по возрастанию, а затем развернуть вектор:

let mut numbers = vec![5, 2, 8, 1, 9];
numbers.sort();
numbers.reverse();
println!("{:?}", numbers); // [9, 8, 5, 2, 1]

Или использовать sort_by() с кастомной функцией сравнения:

numbers.sort_by(|a, b| b.cmp(a));
println!("{:?}", numbers); // [9, 8, 5, 2, 1]

Здесь cmp() возвращает Ordering::Less, Ordering::Equal или Ordering::Greater. Меняя аргументы местами, мы инвертируем порядок.

3. Сортировка по ключу: sort_by_key()

Этот метод принимает замыкание, которое извлекает ключ из каждого элемента. Идеально подходит для сортировки строк по длине:

let mut words = vec!["banana", "apple", "cherry", "date"];
words.sort_by_key(|word| word.len());
println!("{:?}", words); // ["date", "apple", "banana", "cherry"]
// date - 4, apple - 5, banana - 6, cherry - 6

Обратите внимание: если ключи равны (как "banana" и "cherry"), порядок сохраняется (стабильная сортировка).

4. Сортировка структур: sort_by() для сложной логики

Для структур нужно реализовать трейт Ord или использовать sort_by(). Рассмотрим пример с Person:

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Alice".to_string(), age: 30 },
        Person { name: "Bob".to_string(), age: 25 },
        Person { name: "Charlie".to_string(), age: 30 },
        Person { name: "David".to_string(), age: 20 },
    ];

    // Сортировка по возрасту (по возрастанию)
    people.sort_by(|a, b| a.age.cmp(&b.age));
    println!("По возрасту: {:?}", people);

    // Сортировка по возрасту (по убыванию), затем по имени
    people.sort_by(|a, b| {
        // Сначала сравниваем возраст (по убыванию)
        let age_cmp = b.age.cmp(&a.age);
        // Если возраст одинаковый — сравниваем имя
        if age_cmp == std::cmp::Ordering::Equal {
            a.name.cmp(&b.name)
        } else {
            age_cmp
        }
    });
    println!("По возрасту (убыв.) и имени: {:?}", people);
}

5. Трейты Ord и PartialOrd

PartialOrd — частичный порядок. Позволяет сравнивать элементы, но не гарантирует, что любые два элемента можно сравнить (например, числа с плавающей точкой f64: NaN не сравнимо с другими числами).

Ord — полный порядок. Все элементы можно сравнить. Требует реализации PartialOrd, Eq и PartialEq.

Большинство стандартных типов (целые числа, строки, кортежи) реализуют Ord. Для своих структур можно вывести Ord через #[derive(Ord, PartialOrd, Eq, PartialEq)], но порядок будет лексикографическим по полям.

6. Альтернатива: sort_unstable()

Если порядок равных элементов не важен, используйте sort_unstable() — он быстрее (алгоритм quicksort) и потребляет меньше памяти:

let mut numbers = vec![5, 2, 8, 1, 9];
numbers.sort_unstable();
println!("{:?}", numbers); // [1, 2, 5, 8, 9]

Для sort_unstable_by_key() и sort_unstable_by() есть аналоги.

Итог

• sort() — для простой сортировки по возрастанию (стабильная).
• sort_by() — для кастомной логики сравнения.
• sort_by_key() — для сортировки по вычисляемому ключу.
• Для обратного порядка меняйте аргументы местами или используйте reverse().
• Для структур реализуйте Ord или используйте sort_by().

use itertools::Itertools;

fn main() {
    let numbers = vec![5, 2, 8, 1, 9];
    let sorted: Vec<i32> = numbers.iter()
        .sorted_by(|a, b| a.cmp(b))
        .cloned()
        .collect();
    println!("{:?}", sorted); // [1, 2, 5, 8, 9]
    println!("{:?}", numbers); // [5, 2, 8, 1, 9] — исходный не изменился
}

let words = vec!["banana", "apple", "cherry", "date"];
let sorted_by_len: Vec<&str> = words.iter()
    .sorted_by_key(|word| word.len())
    .cloned()
    .collect();
println!("{:?}", sorted_by_len); // ["date", "apple", "banana", "cherry"]