一个要求时间复杂度O(N),空间O(1)的排序问题

Question

一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来的 相对顺序 比如： input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1) 。（此题一直没看到令我满意的答案，一般达不到题目所要求的：时间复杂度O(N),空间O(1)）

Answer 1

找到答案了，来完善一下。
引入两个指针即可，思路如下：

input[] = {1,7,-5,9,-12,15};
pts=&input[i]; pti=&input[i];
n=1;
for(i=0;i<sizeof(input)-2;i++) {
   pts++;
   if (*(pts-1)<0) {
      (pts-2)->next = pts;
      (pts-1)->next = pti;
   }

   if(n && 0>*pti)
      pti++;
   else
      n=0;
}
if (0>input[sizeof(input)-1])
   input[sizeof(input)-1]->next=pti;