用于正负数值排序的该算法是否符合原地（in place）要求？

嗨，我来帮你理清这个问题：你的这个Rearrange函数绝对不是原地（in-place）算法，核心问题就出在你创建的neg和pos两个额外列表上。

先明确下原地算法的核心定义：原地算法要求执行过程中只使用常数级（O(1)）的额外空间——也就是说，除了输入数组本身占用的内存，不能开辟和输入规模成正比的新存储空间。

再拆解你的代码问题：你遍历原数组时，把所有负数和正数分别存入两个新列表，这两个列表的总元素数和原数组完全一致，相当于额外占用了O(n)的空间，这直接违反了原地算法的空间要求。你提到的循环和append操作本身没问题，但这两个新列表的存在才是不符合要求的关键。

如果要实现符合要求的原地O(n)时间复杂度的正负排序，你可以试试双指针的思路：

• 用左指针从数组头部开始找第一个非负数（包括0）
• 用右指针从数组尾部开始找第一个负数
• 交换这两个位置的元素
• 重复这个过程，直到左右指针相遇

给你一个简单的实现示例：

def rearrange_in_place(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        # 左指针定位到第一个非负数
        while left < right and arr[left] < 0:
            left += 1
        # 右指针定位到第一个负数
        while left < right and arr[right] >= 0:
            right -= 1
        # 交换两个位置的元素
        arr[left], arr[right] = arr[right], arr[left]
    return arr

这个实现全程只用到了left、right两个额外变量，空间复杂度是O(1)，而且是原地修改数组，时间复杂度也是O(n)，完全符合你的需求。

内容的提问来源于stack exchange，提问作者fdan