设任意n个整数存放于数组A中，试设计算法，将所有正数拍在所有负数前面

可以使用双指针法来解决这个问题，这是一种常用的排序算法优化策略。这里是一个简单的步骤描述：

1. 定义两个指针，一个 `left` 指向数组的开始，另一个 `right` 初始设置为数组结束减一。

2. 当 `left` 小于等于 `right` 时，执行以下操作：
a. 如果 `A[left]` 是非正数（即不是正数），则左指针 `left` 向右移动一位。
b. 如果 `A[right]` 是正数，说明找到了一个正数应该放置的位置，将它与 `A[right]` 交换，并让右指针 `right` 减一。
c. 继续比较 `left` 和 `right` 的元素，直到找到合适的正数位置。

3. 当 `left` 大于 `right` 时，所有的正数已经被移到了数组的前半部分，剩下的就是负数，整个过程完成。

以下是伪代码的形式：

function sortPositiveNegative(A):
    left = 0
    right = len(A) - 1
    
    while left <= right:
        if A[left] <= 0:
            left += 1
        else:
            swap(A[left], A[right])
            right -= 1
            
    return A

相关问题

用C语言写，设任意n个整数存放于数组A[1…n]中，试设计算法，将所有正数排在所有负数前面（要求： 算法时间复杂度为0(n））。

在C语言中，我们可以使用两个指针分别指向数组的开始（正数区域）和结束（负数区域），然后同时遍历数组。当遇到正数时，就停止移动正数指针，继续向数组末尾移动；当遇到负数时，交换它和正数指针所指向的元素的位置，然后正数指针前进一步。这个过程会一直持续到负数指针到达正数指针的位置，此时所有正数已经按照顺序排列在了前面。

以下是伪代码形式的大致描述：

int A[n], positive = 0, negative = n - 1;
while (positive < negative) {
    if (A[positive] >= 0 && A[negative] < 0) {
        // 交换正数和负数位置
        int temp = A[positive];
        A[positive] = A[negative];
        A[negative] = temp;
        
        // 正数指针前进一位
        positive++;
    } else {
        // 如果正数更大，则直接跳过
        negative--;
    }
}

此算法的时间复杂度确实是 O(n)，因为它只遍历了一次数组。

设任意n个整数存放于数组A[1…n]中，试设计算法，将所有正数排在所有负数前面（要求： 算法时间复杂度为0(n））。用C语言写完整的程序

这个问题可以使用双指针法解决，即分别维护两个指针，一个指向当前查找位置的开始（通常是数组的第一个元素），另一个指向最后一个检查的位置。我们遍历数组，当遇到正数时，就把它移动到开始部分；当遇到负数时，不做调整。这个过程会一直持续到两个指针相遇，或者找到所有的正数。

以下是C语言的一个简单示例：

#include <stdio.h>

void separate_positive_negative(int A[], int n) {
    if (n <= 0) return; // 如果数组为空或长度为0，直接返回

    int i = 0, j = n - 1;
    while (i < j) { // 双指针法
        if (A[i] > 0 && A[j] < 0) { // 同时满足条件交换
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++; j--;
        } else if (A[i] >= 0) { // 遇到正数
            i++;
        } else { // 遇到负数
            j--;
        }
    }
}

int main() {
    int A[] = {5, -3, 7, -2, 0, -8};
    int n = sizeof(A) / sizeof(A[0]);

    printf("Original array:\t");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }

    separate_positive_negative(A, n);

    printf("\nAfter separation:\t");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }

    return 0;
}

运行这个程序，它会将正数移到数组的前半部分，负数移到后半部分，同时保持0值不变。整个过程的时间复杂度为O(n)，因为我们只遍历了一次数组。