原题是这样的：

一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的正负数之间相对顺序。
比如： input: 1,7,-5,9,-12,15 ，ans: -5,-12,1,7,9,15 。且要求时间复杂度O(N),空间O(1) 。

现在提供一种思路：和之前有人提到的桶排序差不多，思路如下

首先找到最大整数Max（15）和最小负数的绝对值Min（12），令M=15+12+1=28，记录整数个数positive_num和负数个数negative_num，则最终排序的结果中，负数的下标范围是[0~negative_num-1]，正数的下标范围是[negative_num, negative_num+positive_num-1]。

1.将所有数字加上|min|,变为非负数，将数组中所有元素都再乘以M。

2. 计算出每个元素 “应该” 在的位置，小于|min| * M 的应该在 [0~negative_num-1]，大于|min| * M 的应该在 [negative_num, negative_num+positive_num-1]

只要将对应位置加上 (数字/ M)。

3. 最后一遍扫描，对数据修正，只需将对应位置进行如下处理： (数字%M - |min|) 即可。

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

    int a[100], i = 0, n;

    int positive_num, negative_num;

    int min, max;

    int M;

    while (cin >> n)

    {

        memset(a,0,sizeof(a));

        positive_num = negative_num = 0;

        min = max = 0;

        for (i = 0; i < n; i++)

        {

            cin >> a[i];

            if (a[i] > 0)

            {

                ++positive_num;

                if (a[i] > max) max = a[i];

            }

            else

            {

                ++negative_num;

                if (a[i] < min) min = a[i];

            }

        }

        M = max + (-min) + 1; // M = max + |min| + 1

        for (i = 0; i < n; i++)

        {

            a[i] += (-min);  // 为方便求余，每个位置加上(-min)，则数组中元素都变为非负数。

            a[i] *= M;

        }

        int negative_ptr = 0;

        for (i = 0; i < n; i++)   //处理负数

        {

            if (a[i] < M * (-min))

            {

                a[negative_ptr] += a[i] / M;

                ++negative_ptr;

            }

        }

        int positive_ptr= negative_num; //处理正数

        for (i = 0; i < n; i++)

        {

            if (a[i] > M * (-min))

            {

                a[positive_ptr] += a[i] / M;

                ++positive_ptr;

            }

        }

        for (i = 0; i < n; i++)  //还原

        {

            a[i] = a[i] % M - (-min);

        }

        for (i = 0; i < n; i++)  //输出

        {

            cout << a[i] << " ";

        }

        cout << endl;

    }

    return 0;

}