我要寻找对C算法（或code）实现快速排序的整数数组相交/联合运营。越快越好。

I am looking for C algorithms (or code) that implement fast sorted integer array intersection/union operations. The faster, the better.

在换句话说，在C一种有效的方式来实现整数两个阵列之间并和交操作？

In other words, what's an efficient way in C to implement union and intersection operations between two arrays of integers?

推荐答案

假设这些都是实际的设置的（因为有重复阵列上的交叉点是有问题的最好），以下code也许会有帮助。

Assuming that these are actual sets (since an intersection on arrays with duplicates is problematic at best), the following code may help.

首先，一些必要的头文件：

First, some requisite headers:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

和一些强制性的文件：

// Description:
//     Will give back the union or intersection of two sorted integer
//         sets (only one copy of each element).
//     Caller responsible for freeing memory.
// Input:
//     Union ('u') or intersection (anything else).
//     arr1 and arr2 are pointers to the arrays.
//     sz1 and sz2 are the number of integers in each array.
//     psz3 as the pointer to the variable to receive the
//         size of the returned array.
// Returns:
//     A pointer to the array, or NULL if malloc failed.
//     Memory allocated even if result set is empty, so
//        NULL return indicates ONLY malloc failure.
//     psz3 receives the size of that array, which is
//        zero for an empty set.

然后函数正确的：

Then the function proper:

int *arrUnionIntersect ( int type,
    int *arr1, size_t sz1,
    int *arr2, size_t sz2,
    size_t *psz3
) {
    int *arr3, *ptr1, *ptr2;

    *psz3 = 0;

    // If result will be empty, just return dummy block.

    if ((sz1 == 0) && (sz2 == 0))
        return malloc (1);

    // Otherwise allocate space for real result.

    if (type == 'u')
        arr3 = malloc ((sz1 + sz2) * sizeof (*arr1));
    else
        if (sz1 > sz2)
            arr3 = malloc (sz1 * sizeof (*arr1));
        else
            arr3 = malloc (sz2 * sizeof (*arr1));
    if (arr3 == NULL)
        return NULL;

直到那里，它主要是用于初始化的功能。这下有点穿越两个输入集，选择什么被添加到结果。这是最好的做法（在我看来）三个阶段，当两个输入集仍然有一些剩余的元素的第一个是选择。请注意，不同的行为，这里的工会和路口，特别是十字路口只有元素添加的，如果它在的两个的输入设置：

    // Set up pointers for input processing.

    ptr1 = arr1;
    ptr2 = arr2;

    // Phase A: select appropriate number from either, when both
    //    have remaining elements.

    while ((sz1 > 0) && (sz2 > 0)) {
        if (*ptr1 == *ptr2) {
            arr3[(*psz3)++] = *ptr1++;
            sz1--;
            ptr2++;
            sz2--;
            continue;
        }

        // We don't copy for intersect where elements are different.

        if (*ptr1 < *ptr2) {
            if (type == 'u')
                arr3[(*psz3)++] = *ptr1;
            ptr1++;
            sz1--;
            continue;
        }

        if (type == 'u')
            arr3[(*psz3)++] = *ptr2;
        ptr2++;
        sz2--;
    }

的其他两相（其中只有一个将运行工会，并没有对交叉点），只是获取从非空输入设定其余的项目：

The other two phases (of which only one will run for unions, and none for intersections), simply gets the remaining items from the non-empty input set:

    // Phase B and C are only for unions.

    if (type == 'u') {
        // Phase B: process rest of arr1 if arr2 ran out.

        while (sz1 > 0) {
            arr3[*psz3++] = *ptr1++;
            sz1--;
        }

        // Phase C: process rest of arr2 if arr1 ran out.

        while (sz2 > 0) {
            arr3[*psz3++] = *ptr2++;
            sz2--;
        }
    }

    // Return the union.

    return arr3;
}

和测试程序：

int main (void) {
    int x1[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int x2[] = {2, 3, 5, 7, 11, 13, 17, 19};
    size_t i, sz3;
    int *x3;

    x3 = arrUnionIntersect ('u', x1, sizeof(x1)/sizeof(*x1),
        x2, sizeof(x2)/sizeof(*x2), &sz3);
    printf ("union =");
    for (i = 0; i < sz3; i++)
        printf (" %d", x3[i]);
    free (x3);
    printf ("\n");

    x3 = arrUnionIntersect ('i', x1, sizeof(x1)/sizeof(*x1),
        x2, sizeof(x2)/sizeof(*x2), &sz3);
    printf ("intersection =");
    for (i = 0; i < sz3; i++)
        printf (" %d", x3[i]);
    free (x3);
    printf ("\n");

    return 0;
}

随着它的输出，符合市场预期：

along with its output, as expected:

union = 1 2 3 5 7 9 11 13 15 17 19
intersection = 3 5 7 11 13 17 19