2

设计一个线性算法来重新排列给定的 n 个元素数组的元素，使其所有负数在任何零之前，并且任何零在任何正数之前。它还应该节省空间，以便它不需要超过恒定数量的额外空间。

我想到的一切都比 大得多O(n)，并且会喜欢一些提示/提示/帮助/java代码！

4

3 回答 3

2

帮助？提示：快速排序的分区部分，枢轴为0. 请参阅此 Wikipedia 文章，查找就地版本。

我刚刚意识到，如果您实施上面链接中给出的确切版本，如果您的欺骗为零，则可能无济于事。我的说法仍然正确，您需要使用 Quicksort 的分区部分，但分区将通过荷兰国旗问题或三路分区来完成。这是给你的伪代码

//假设索引为1
A[1..n]
p = 0
q = n+1
我 = 1

当 i < q
  如果 A[i] < 0
   交换（我，++p）
  否则如果 A[i] > 0
   交换（我，--q）
  别的
   我++

时间复杂度：    O(n)
空间复杂度：O(1)

于 2012-10-22T04:59:51.473 回答
2

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

于 2012-10-22T04:59:54.457 回答
1

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

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

通过第二次迭代，您将根据它们的范围交换项目（从第一个开始）到适当的索引，然后增加索引。

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

于 2012-10-22T09:02:37.307 回答