Программа Javascript для перестановки положительных и отрицательных чисел за время O (n) и дополнительное пространство O (1)

Массив содержит как положительные, так и отрицательные числа в случайном порядке. Переставьте элементы массива так, чтобы положительные и отрицательные числа располагались попеременно. Количество положительных и отрицательных чисел не обязательно должно быть равным. Если положительных чисел больше, они появляются в конце массива. Если отрицательных чисел больше, они тоже появляются в конце массива.
Например, если входной массив [-1, 2, -3, 4, 5, 6, -7, 8, 9], то выход должен быть [9, -7, 8, -3, 5, - 1, 2, 4, 6]
Примечание. Процесс разделения изменяет относительный порядок элементов. Т.е. порядок появления элементов при таком подходе не сохраняется. См. это для соблюдения порядка появления элементов в этой задаче.
Решение состоит в том, чтобы сначала разделить положительные и отрицательные числа, используя процесс разделения QuickSort. В процессе разделения рассматривайте 0 как значение элемента поворота, чтобы все отрицательные числа помещались перед положительными числами. Как только отрицательные и положительные числа разделены, мы начинаем с первого отрицательного числа и первого положительного числа и заменяем каждое альтернативное отрицательное число следующим положительным числом.

Выход:

    4   -3    5   -1    6   -7    2    8    9

Временная сложность: O(n), где n — количество элементов в данном массиве. Поскольку мы используем цикл для прохождения N раз, это будет стоить нам O (N) времени.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.

Пожалуйста, обратитесь к полной статье о перестановке положительных и отрицательных чисел за время O (n) и дополнительное пространство O (1) для получения более подробной информации!