设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0(n)）。（难度系数2）

可以采用双指针的方法，一个指针指向数组的开头，一个指针指向数组的末尾，然后从两端向中间扫描。

当左指针指向的数为负数且右指针指向的数为正数时，交换两个数的位置，然后继续向中间扫描。

当左指针指向的数为正数时，左指针向右移动一位。

当右指针指向的数为负数时，右指针向左移动一位。

直到左指针和右指针相遇为止，所有正数就排在了所有负数前面。

下面是具体的实现代码：

void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

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

相关问题

数据结构中设任意n个整数存放于数组A（1:n）中，试编写算法，将所有正数排在所有负数面前

好的，这是一个关于数据结构的问题，我会尽力回答。可以使用双指针的方法，一个指向数组的开头，一个指向数组的结尾，从两端开始遍历数组，如果左边是负数，右边是正数，则交换它们的位置。重复这个过程直至两个指针相遇。以下是具体的实现代码：

def rearrange_array(arr):
    left = 0
    right = len(arr) - 1
    
    while left < right:
        while arr[left] < 0:
            left += 1
        while arr[right] >= 0:
            right -= 1
            
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
    
    return arr

这个算法的时间复杂度为O(n)，因为只需要遍历整个数组一次。

设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0(n)）。

可以使用双指针的方法，设置一个指针指向数组的起始位置，另一个指针指向数组的末尾位置，然后不断交换它们指向的元素，直到指针相遇为止。具体步骤如下：

1. 初始化左指针p为1，右指针q为n。

2. 当p<q时，执行以下操作：

- 如果A[p]为正数，p向右移动一位。

- 如果A[p]为负数，A[p]和A[q]交换，q向左移动一位。

- 如果A[q]为负数，q向左移动一位。

- 如果A[q]为正数，A[q]和A[p]交换，p向右移动一位。

3. 当p=q时，排序完成。

这个算法的时间复杂度为O(n)，因为每个元素只会被访问常数次，所以具有较高的效率。