algorithm - 按相对位置对数组排序

Question

给定一个包含负整数和正整数的数组，实现一个花费 O(n) 时间和 O(1) 空间的算法，使所有负整数排在所有正整数前面，并保持相对位置。例如:{1,7,-5,9,-12,15} -----> {-5,-12,1,7,9,15}

你有什么想法吗？

Answer 1

您要求的是稳定的就地分区函数。

论文Stable Minimum Space Partitioning in Linear Time (1992)声称有这样的算法，但有些other所以 questions对其可行性提出了质疑。