Big-Theta(n)线性排序算法？

Question

设计一个线性算法来重新排列给定n个元素数组中的元素，使其所有负数都在任何零之前，而任何零在任何正数之前。它还应该是空间高效的，因此它不需要超过恒定数量的额外空间。

我所考虑的一切都比O(n)大得多，我想要一些提示/提示/帮助/java代码！

Answer 1

看看基数排序的修改版本，唯一可以在线性时间内工作的排序是基于非比较的排序(因此列表/数组中的条目不会相互比较)，所以这是另一种需要查看的东西(证明涉及最小高度的比较树，为什么比较项的排序总是至少为nlogn)。

Answer 2

如果您只需要根据3个范围重新排列项目，则为负零和正。

一个简单的解决方案是使用单次数组迭代(O(n))计算负数、零和正数项的数量(实际上，如果您已经知道数组的大小，则不需要计算正数项的数量)。

在第二次迭代中，您将根据项目的范围将项目(从第一个项目开始)交换到适当的索引，然后增加索引。

就是这样，没有额外的内存和teta(n)时间复杂度。