Question

在限定时间复杂度O（n）,空间复杂度O（1）条件下，对数组排序。要求大于0元素的在数字0左边，小于

在限定时间复杂度O（n）,空间复杂度O（1）条件下，对数组排序。要求大于0元素的在数字0左边，小于0的元素在数组右边，0元素在中间。而对大于0的元素之间，或者小于0的元素之间并不要求排序。
我想到类似于快排的一趟，但是具体结果总是出不来～大神求助。

Answer 1

不知道数字的总量吗？
是否队首队尾指针相等，是则结束循环。
如果队首小于0，则观察队尾。
队尾大于0，则交换队首队尾。小于则，队尾保留，向队首移动1个比较直至可以交换。
等于0则

如果队尾指针为下一个队首指针的位置，则只比较和交换。
否则，交换该元素和其下一个元素。且不移动队尾指针。
如果队首大于0，则向队尾移动1个继续比较。

如果队首等于0，
如果队尾指针为下一个队首指针的位置，则只比较和交换。
否则，交换该元素和其下一个元素。且不移动队首指针。

由于0元素的存在和无法确定的数组长度，导致我想出来的这个破东西的时间复杂度大概是n+n/2
好像还是算作n的。

追问

先谢谢你。
能否给个代码呢？C,java都能看得懂。
你需要描述的话我等于0的地方看不懂额。

追答

关于0的部分。由于空间限定为1，所以只能进行交换对调。在发现元素0时，需要把0移动到中间位置。由于数组长度不确定，0元素只能跟着首尾指针一起向中间移动。举个例子吧
现有数组-1,0，-2,1
开始
首=-1尾=1
交换结果1,0，-2,-1
首=0尾=-2
交换结果1,-2,0，-1
首=-2，尾=0
交换结果1,0,-2,-1
首=-2，尾=-2
结束。

Answer 2

大神大声的告诉我什么排序方法的平均时间复杂度是O(n)?

追问

没说么……这个只是分块排序