Метод select_nth_unstable

Метод select_nth_unstable переставляет элементы среза таким образом, что элемент с индексом n занимает позицию, которую он занимал бы в полностью отсортированном срезе. При этом все элементы слева от него меньше или равны ему, а все элементы справа - больше или равны. В отличие от полной сортировки, этот метод работает за линейное время. Параметром метод принимает индекс n - позицию, на которую нужно поставить «n-й по порядку» элемент. Метод возвращает кортеж из трёх срезов: элементы до индекса n, сам элемент и элементы после индекса.

Синтаксис

slice.select_nth_unstable(n)

Пример

Давайте расставим элементы вектора vec![5, 2, 8, 1, 4] так, чтобы элемент с индексом 2 оказался на своём месте:

fn main()
{
	let mut vec = vec![5, 2, 8, 1, 4];
	let (left, mid, right) = vec.select_nth_unstable(2);
	println!("left: {:?}", left);
	println!("mid: {:?}", mid);
	println!("right: {:?}", right);
	println!("vec: {:?}", vec);
}

Результат выполнения кода:

left: [2, 1]
mid: 4
right: [8, 5]
vec: [2, 1, 4, 8, 5]

Пример

Давайте найдём медианный элемент вектора vec![9, 1, 7, 3, 5], поставив его в середину:

fn main()
{
	let mut vec = vec![9, 1, 7, 3, 5];
	let mid_index = vec.len() / 2;
	let (_, median, _) = vec.select_nth_unstable(mid_index);
	println!("median: {}", median);
}

Результат выполнения кода:

median: 5

Смотрите также

метод sort,
который сортирует срез по возрастанию
метод sort_unstable,
который сортирует срез неустойчивой сортировкой
метод binary_search,
который ищет элемент в отсортированном срезе
метод is_sorted,
который проверяет, отсортирован ли срез