Алгоритмы сортировки являются фундаментальными инструментами в информатике, и поиск наиболее эффективного из них для конкретной задачи имеет решающее значение. В этой статье блога мы рассмотрим различные алгоритмы сортировки, реализованные в Rust, попутно предоставляя примеры кода. Независимо от того, являетесь ли вы новичком или опытным разработчиком Rust, это руководство поможет вам понять и эффективно реализовать алгоритмы сортировки.
- Пузырьковая сортировка.
Пузырьковая сортировка – это простой алгоритм сортировки на основе сравнения. Он неоднократно меняет местами соседние элементы, если они расположены в неправильном порядке, пока не будет отсортирован весь список. Вот реализация в Rust:
fn bubble_sort<T: Ord>(arr: &mut [T]) {
let len = arr.len();
for i in 0..len {
for j in 0..len - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
}
}
}
}
- Сортировка выбором:
Сортировка выбором делит входные данные на отсортированную и несортированную область. Он неоднократно выбирает наименьший элемент из неотсортированной области и заменяет его самым левым элементом неотсортированной области. Вот реализация на Rust:
fn selection_sort<T: Ord>(arr: &mut [T]) {
let len = arr.len();
for i in 0..len {
let mut min_index = i;
for j in i + 1..len {
if arr[j] < arr[min_index] {
min_index = j;
}
}
arr.swap(i, min_index);
}
}
- Сортировка вставками.
Сортировка вставками создает окончательный отсортированный массив по одному элементу за раз. Он сравнивает каждый элемент с ранее отсортированной частью массива и вставляет его в правильную позицию. Вот реализация на Rust:
fn insertion_sort<T: Ord>(arr: &mut [T]) {
for i in 1..arr.len() {
let key = arr[i];
let mut j = i;
while j > 0 && arr[j - 1] > key {
arr[j] = arr[j - 1];
j -= 1;
}
arr[j] = key;
}
}
- Сортировка слиянием.
Сортировка слиянием — это алгоритм «разделяй и властвуй», который делит входные данные на более мелкие подзадачи, сортирует их, а затем объединяет отсортированные подмассивы для получения окончательного отсортированного массива. Вот реализация на Rust:
fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
if arr.len() <= 1 {
return;
}
let mid = arr.len() / 2;
merge_sort(&mut arr[..mid]);
merge_sort(&mut arr[mid..]);
merge(arr, mid);
}
fn merge<T: Ord + Clone>(arr: &mut [T], mid: usize) {
let mut left = arr[..mid].to_vec();
let mut right = arr[mid..].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = 0;
while i < left.len() && j < right.len() {
if left[i] <= right[j] {
arr[k] = left[i].clone();
i += 1;
} else {
arr[k] = right[j].clone();
j += 1;
}
k += 1;
}
while i < left.len() {
arr[k] = left[i].clone();
i += 1;
k += 1;
}
while j < right.len() {
arr[k] = right[j].clone();
j += 1;
k += 1;
}
}
В этой статье мы рассмотрели несколько алгоритмов сортировки, реализованных в Rust. Пузырьковая сортировка, сортировка выбором, сортировка вставками и сортировка слиянием — это лишь несколько примеров из множества доступных алгоритмов сортировки. Каждый алгоритм имеет свои сильные и слабые стороны, и понимание их характеристик необходимо для выбора подходящего для ваших конкретных потребностей. Благодаря знаниям, полученным из этого руководства, вы будете хорошо подготовлены к эффективной реализации алгоритмов сортировки в Rust.