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

Question

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

我创建了一个时间复杂度为 O(n^2) 的原始函数，但想知道您将如何在线性时间内解决它？我的算法使用两个指针开始指向数组的最左边和最右边的元素。当ptr1遇到正值，ptr2遇到负值时，我们进行swap，指针迭代right/left，遇到时函数returns，因为数组已经收集完毕。

你能帮我想一个更简单的算法来做这个收集吗？

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++ 编写 std::partition 的 C 版本，这已经是线性的。

链接了示例 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;
        }
    }
}

唯一的技巧是注意

在你进入循环之前，根据定义，半开区间 [array,first) 中的每个元素都是负数（这是你找到的第一个正值）
每次你发现一个不合适的负值，并且在你将它与 *first 交换并增加指针后，这种情况再次成立（就你目前所知）。

也就是说，区间[array, i)总是在循环开始时划分，[array, i]总是在循环结束时划分。

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

How to partition array in-place in C with O(n) algorithm?

c

arrays

sorting

algorithm

complexity-theory