数据结构：编写算法，对n个关键字取整数的记录进行整理，以使得所有关键字为负值的记录排在关键字为非负值的记录之前。要求：采用顺序存储结构，至多使用一个记录的辅助存储空间；算法的时间复杂度为O(n)。

算法思路：

1. 首先定义两个指针，分别指向数组的头和尾。

2. 从头开始遍历数组，如果当前关键字为负值，则将该记录与头指针所指的记录交换，并将头指针向后移动一位。

3. 如果当前关键字为非负值，则将该记录与尾指针所指的记录交换，并将尾指针向前移动一位。

4. 重复步骤2和步骤3，直到头指针和尾指针相遇为止。

算法实现：

void rearrange(int A[], int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        while (i < j && A[i] < 0) i++;
        while (i < j && A[j] >= 0) j--;
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
}

算法分析：

该算法的时间复杂度为O(n)，因为只需要遍历一次数组即可完成整理。同时，由于只使用了一个记录的辅助存储空间，空间复杂度为O(1)。