Перемещение всех нулевых элементов в конец последовательности

Условие

Дан массив, состоящий из неотрицательных целых чисел. Требуется перенести все элементы, равные нулю, в конец массива, при этом порядок остальных элементов должен остаться неизменным. Пример: 0 1 0 2 0 3 => 1 2 3 0 0 0

Ответ

За один проход перепишите все ненулевые элементы в начало, сохраняя порядок, а оставшуюся часть заполните нулями. Потребуются O(n) времени и O(1) дополнительной памяти.

void moveZeros(std::vector<int>& values) {
    std::size_t write = 0;
    for (int value : values)
        if (value != 0) values[write++] = value;
    std::fill(values.begin() + write, values.end(), 0);
}

Индекс записи никогда не опережает чтение, поэтому ещё не обработанные элементы не затираются. Пример превращается в 1, 2, 3, 0, 0, 0. Пустой массив и массив из одних нулей также обрабатываются. Метод фактически подходит и для отрицательных ненулевых чисел.