如何使用 O(n) 算法在 C 中就地分区数组？

Question

我想对整数数组进行分区，以便负值位于正值的左侧，并且我想就地执行此操作（无需额外的辅助内存）。请注意，数组不能从小到低排序，只需将负数收集到左侧，将正数收集到右侧。

我创建了一个时间复杂度为 O(n^2) 的朴素函数，但想知道如何在线性时间内解决它？我的算法使用两个指针，开始指向数组的最左边和最右边的元素。当 ptr1 遇到正值，而 ptr2 遇到负值时，我们执行交换，指针向右/向左迭代，当它们相遇时，函数返回，因为数组已完成收集。

你能帮我想出一个更简单的算法来进行这种收集吗？

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;
                }
             }
         }
    }
}

Answer 1

你想要的是线性时间分区，而不是排序。本质上是从 C++ 编写一个 C 版本std::partition，它已经是线性的。

链接了一个示例 C++ 实现，但它很容易翻译。速写：

/*
 * Quick translation of C++ std::partition<int*>.
 *
 * You just need to write the helper functions
 *
 *     int* find_first_positive(int *array, size_t length)
 *     -- should return array+length if they're all negative
 *
 *     void swap(int*, int*)
 *     -- just exchange the two integers
 */
void sign_partition(int *array, size_t length)
{
    int *last = array + length;
    int *first = find_first_positive(array, length);
    if (first == last) return; /* all negative, nothing to do */

    /* now search for negative values after the first positive */
    for (int *i = first + 1; i != last; ++i) {
        if (*i < 0) {
            swap(i, first);
            ++first;
        }
    }
}

唯一的技巧是注意

1. 在进入循环之前，根据定义，半开区间中的每个元素[array,first)都是负数（这是您找到的第一个正值）

2. 每当你发现一个负值不合适时，在你交换它并*first增加指针之后，这个条件再次成立（据你目前所知）。

   也就是说，间隔[array, i)始终在循环开始时分区，并且[array, i]始终在循环结束时分区。