要在恒定的空间（但二次时间）中实现此结果，可以通过在数组的每一端放置一个队列来使用双队列方法（类似于荷兰国旗算法）。从左到右读取项目：将项目添加到左侧队列意味着将其保留，将项目添加到右侧队列意味着将不在队列中的所有元素向左移动一个，并将添加的项目放在末尾。然后，要连接队列，只需反转第二个队列中元素的顺序即可。

这样最多可以执行O（n）次操作（将元素左移）O（n）次，从而产生O（n²）运行时间。

通过使用类似于合并排序的方法，可以降低O（n log n）的复杂度：将数组切成两半，以形式递归地对它们进行排序，[N P] [N P]然后在O（n）时间中将第一个P与第二个交换N（当它们的尺寸不完全相同时，会变得有些棘手，但它仍然是线性的。

我绝对不知道该如何减少O（n）的时间。

编辑 ：实际上，您的链表见解是正确的。如果将数据作为双链表提供，则可以在O（n）时间，O（1）空间中实现两队列策略：

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

使用保持指向第一个元素和最后一个元素的指针的链表实现，然后pop，append和concatenate都是O（1）操作，因此总复杂度为O（n）。至于空间，没有任何操作分配任何内存（仅使用pop释放的内存），因此总体上为O（1）。