有n个无序非零整数，不要求排好序，写出将负数排在正数之前的o（n）时间复杂度的算法。

可以使用双指针法，一个指针从数组头部向尾部扫描，另一个指针从数组尾部向头部扫描，当两个指针相遇时，扫描结束。具体步骤如下：

1. 初始化左右指针left和right，left指向数组头部，right指向数组尾部。

2. 当left指向的数小于0时，left向右移动，继续检查下一个数。

3. 当right指向的数大于等于0时，right向左移动，继续检查前一个数。

4. 如果left指向的数大于等于0，right指向的数小于0，交换left和right指向的数。

5. 重复2-4步，直到left和right指针相遇。

代码实现如下：

void rearrange(int arr[], int n)
{
    int left = 0, right = n - 1;
    while (left < right) {
        while (arr[left] < 0 && left < right)
            left++;
        while (arr[right] >= 0 && left < right)
            right--;
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

这个算法的时间复杂度为O(n)，空间复杂度为O(1)。