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

为了将数组中的所有正数排在负数之前，并保持时间复杂度为O(n)，我们可以使用双指针法。这里是一个简单的步骤描述：

1. 定义两个指针，一个 `left` 从数组开始，另一个 `right` 到数组结尾。

2. 当 `left` 指针小于 `right` 指针时，执行以下操作：
a. 如果 `A[left]` 是正数，将其与 `A[right]` 进行交换，然后向左移动 `left` 指针。
b. 否则，如果 `A[left]` 是负数，向右移动 `right` 指针。

3. 当 `left` 和 `right` 相遇时，遍历结束，因为所有的正数都已经被放置到了前半部分，剩余的就是负数。

以下是这个算法的伪代码实现：

function separatePositiveNegative(A):
    left = 0
    right = length(A) - 1
    
    while left < right:
        if A[left] >= 0:
            # 交换左侧正数和右侧的任意元素
            temp = A[left]
            A[left] = A[right]
            A[right] = temp
            right -= 1
        else:
            left += 1

    return A