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]