python - 这个算法是否占用了太多的额外空间，成为 "in place"？

Question

作业是对向量中的负数和正数进行排序。问题是该算法必须是 O(n) 并且到位。
我的“解决方案”是:

def Rearrange(arr):
    neg = []
    pos = []
    for x in arr:
        if x < 0:
            neg.append(x)
        else:
            pos.append(x)
    return neg + pos

所以，我想知道这个算法是否到位？我知道循环和追加操作满足就地算法。但是存储值的列表又如何呢？它是否使用了太多额外空间来满足就地算法？如果确实如此，是否有一个简单的方法可以解决这个明显的问题？现在我有点陷入困境。

Answer 1

是否需要对整个数组进行排序，或者只是左侧为负值，右侧为正值(和 0)？

如果你想要实现的是第二件事，那么下面的函数应该可以工作(它可以就地工作，并且时间复杂度为 O(n)):

def rearrange(array):

    left = 0
    right = len(array) - 1

    while left < right:
        if array[left] >= 0 > array[right]:
            array[right], array[left] = array[left], array[right]
            left += 1
            right -= 1
        elif array[left] < 0:
            left += 1
        else:
            right -= 1

>>> array = [-5, 6, 7, -4, 2, 0, -1]
>>> rearrange(array)
>>> array 
[-5, -1, -4, 7, 2, 0, 6]