请求验证：将负元素移至数组末尾的代码的时间与空间复杂度

DevOps 小满

2026-8-5

问题解答

你的分析完全正确，以下是具体验证：

时间复杂度：O(N²)

外层循环会遍历数组的每个元素，最多执行N次（N为数组长度）。
每当遇到负元素时，内层循环需要通过多次交换将该元素移动到当前的末尾位置（由k标记）。最坏情况下（比如数组全是负数），内层循环的总执行次数为1+2+...+(N-1) = N(N-1)/2，这属于O(N²)的时间量级。
因此整体时间复杂度为O(N²)，和你的判断一致。

空间复杂度：O(1)

代码仅使用了k、n、i、j、temp这几个临时变量，所有操作都直接在输入数组上进行，没有额外开辟与数组规模相关的存储空间。
所以空间复杂度为O(1)，你的分析准确。

代码实现

public static void MoveNegativeElementsToEnd(int arr[])
{
    int k=arr.length-1;
    int n=arr.length;

    for(int i=n-1;i>=0;i--){
        if(arr[i]<0){
            for(int j=i;j<k;j++){
                swap(arr,j,j+1);
            }
            k--;
        }
    }
}
public static void swap(int[] arr, int a, int b){
    int temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;
}