设任意n个整数存放于数组A[1..n]中,试编写算法,将所有整数排在所有负数前面(要求:算法时间复杂度为O(n))。

可以使用双指针法，一个指向数组的头部，一个指向数组的尾部，分别向中间移动。具体步骤如下：

1. 初始化两个指针i和j，i指向数组的头部，j指向数组的尾部。

2. 当i<j时，执行以下操作：

（1）如果A[i]为负数，则将i向后移动一位；

（2）如果A[i]为正数，则判断A[j]的符号：

a. 如果A[j]为负数，则将A[i]和A[j]交换，然后将i向后移动一位，j向前移动一位；

b. 如果A[j]为正数，则将j向前移动一位。

3. 当i>=j时，算法结束。

代码实现如下：

void moveNegative(int A[], int n){
    int i = 0, j = n - 1;
    while(i < j){
        if(A[i] < 0){
            i++;
        }
        else{
            if(A[j] < 0){
                //swap A[i] and A[j]
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
                j--;
            }
            else{
                j--;
            }
        }
    }
}

时间复杂度为O(n)，空间复杂度为O(1)。