如何在C语言中用O(n)算法原地划分整数数组（负数左正数右）

你提到的双指针思路本身完全可以实现**O(n)**的线性时间复杂度，但你当前的实现因为嵌套了两层循环，才变成了O(n²)。咱们可以简化逻辑，要么一次遍历完成，要么调整双指针的移动方式，避免嵌套循环，都能高效完成划分。

先看看你原来的实现代码：

int* swaps(int* array){ 
    int* ptr1; 
    ptr1 = &array[0]; 
    int* ptr2; 
    ptr2 = &array[N-1]; 
    int tmp; 
    for(ptr1; ptr1 <= &array[N-1]; ptr1++){ 
        if(ptr1==ptr2){ 
            return array; 
        } 
        if(*ptr1 >= 0){ 
            for(ptr2; ptr2 >= &array[0]; ptr2--){ 
                if(ptr1==ptr2){ 
                    return array; 
                } 
                // swap elements 
                if(*ptr2 < 0){ 
                    tmp = *ptr2; 
                    *ptr2 = *ptr1; 
                    *ptr1 = tmp; 
                    ptr2--; 
                    if(ptr1==ptr2){ 
                        return array; 
                    } 
                    break; 
                } 
            } 
        } 
    } 
}

这个实现的问题在于：当左指针ptr1遇到正数时，会启动一个从右往左的嵌套循环找负数，最坏情况下（比如数组全是正数），每个左指针位置都要遍历整个右半部分，时间复杂度直接变成了O(n²)。

优化方案1：单遍历的双指针实现 #

这个思路更简洁：用一个指针left标记下一个负数应该放置的位置，另一个指针right遍历整个数组，遇到负数就和left位置的元素交换，然后left右移。整个过程只遍历数组一次，时间复杂度O(n)，空间复杂度O(1)。

void partitionNegativesLeft(int* array, int n) {
    int left = 0; // 标记下一个负数要存放的位置
    for (int right = 0; right < n; right++) {
        if (array[right] < 0) {
            // 交换当前负数到left位置
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            left++;
        }
    }
}

优化方案2：左右向中间逼近的双指针实现 #

如果你更偏好左右指针向中间移动的思路，也可以调整逻辑，避免嵌套循环，同样实现O(n)时间：

void partitionNegativesLeftTwoPointers(int* array, int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        // 左指针找到第一个正数
        while (left < right && array[left] < 0) {
            left++;
        }
        // 右指针找到第一个负数
        while (left < right && array[right] >= 0) {
            right--;
        }
        // 交换两者，然后指针向中间移动
        if (left < right) {
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
            left++;
            right--;
        }
    }
}

这里的两个内部while循环不会重复遍历元素，因为每个指针只会向中间移动，不会回头，所以整体还是线性时间复杂度，比你原来的嵌套循环简洁高效得多。

补充说明 #

• 两种实现都不会对负数或正数内部进行排序，只是完成“负数左、正数右”的划分，完全符合你的需求。
• 都是原地操作，不需要额外辅助数组，空间复杂度为O(1)。

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