如何在不改变相对位置的情况下，将一个整数数组排序为负的、零的、正的部分?

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence. for example: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}Give an O(n) algorithm which takes as input an