Есть ли способ разбить вектор на нечетные и четные числа на месте?

Question

Есть ли простой способ найти все четные числа и переместить их все в конец вектора? Порядок не имеет значения, все, что имеет значение, так это то, что четы были перенесены до конца. Тем не менее, было бы хорошо , если порядок был сохранен.

Например: [1, 2, 3, 4, 5] => [1, 3, 5, 2, 4]

Я хотел бы иметь подпись pub fn move_by_filter(nums: &mut Vec<i32>).

Я попытался отфильтровать и объединить векторные фрагменты, но столкнулся с проблемой объединения фрагментов массива:

let evens = nums.iter().filter(|&&i| i % 2 == 0).collect::<Vec<_>>();

let odds = nums.iter().filter(|&&i| i % 2 != 0).collect::<Vec<_>>();

// then I want to do something like: nums = odds.push(evens)

Это не push их до конца vector.

Я не уверен, что это лучший подход, так как я должен использовать iter() дважды (что, я думаю, O (N) + O (N), но я хотел бы сделать это в одна операция, если это возможно)

Answer 1

Самое простое решение - отсортировать вектор с помощью специального ключа сортировки:

pub fn sort_by_parity(nums: &mut [i32]) {
    nums.sort_by_key(|&x| x % 2 == 0);
}

Стандартный алгоритм сортировки Rust стабилен, поэтому при этом будет сохранен исходный порядок нечетных и четных чисел.

Закрытие, переданное для создания ключей сортировки, оценивается как false для нечетных чисел и true для четных чисел. Это гарантирует, что все нечетные числа будут отсортированы перед четными числами.

Вместо того, чтобы принимать изменяемую ссылку на вектор, эта функция принимает изменяемую ссылку на фрагмент, который более обобщенный c.

Время выполнения этого подхода - O (n log n), что не является оптимальным для разделения на месте. Вы можете достичь линейного времени выполнения O (n), например, используя метод partition():

pub fn partition_by_parity(nums: &mut [i32]) {
    let (even, odd): (Vec<_>, Vec<_>) = nums.iter().partition(|&x| x % 2 == 0);
    nums[..odd.len()].copy_from_slice(&odd);
    nums[odd.len()..].copy_from_slice(&even);
}

Разница во времени выполнения между двумя подходами на практике вряд ли имеет значение.

Если вам не требуется сохранять исходный порядок нечетных и четных элементов, вы можете разделить срез на месте за линейное время, не требуя дополнительного буфера. Rust Nightly предлагает нестабильный метод partition_in_place() для этой цели, но это не так уж сложно реализовать самостоятельно - это в основном шаг разделения в Quicksort.