o表示法和合并两个已经排序的数组

Question

有人告诉我，在线性时间内，将两个已经排序的大小不同的数组A和B合并成一个数组C。

通过线性时间，我明白了这个算法的时间复杂度必须是O（n）。后来，我还被告知在合并数组时执行排序。

我的一个想法是创建一个算法，在两个数组中都有两个指针，指向最小的元素。指向的最小元素将进入新数组。当一个数组耗尽时，另一个数组的剩余元素将复制到新数组中。

由于几个月前我刚开始编程，我发现这很难实现，因此我决定执行合并排序（MS），因为它与上述算法最相似。然而，我关心的是MS本身的时间复杂性-O（nlogn）

然而，鉴于两个阵列已经排序，MS的时间复杂度会降低还是保持不变？

先谢谢你。

Answer 1

将两个已经排序的数组，大小不同的数组，A 和 B 合并为一个数组，C 以线性时间。

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

https://godbolt.org/z/PY8Ysv319

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void sort(int *array, size_t size)
{
    qsort(array, size, sizeof(array[1]), cmpfunc);
}

int *mergeArrays(const int *array1, const int *array2, size_t size1, size_t size2, int asc)
{
    int *result = malloc((size1 + size2) * sizeof(*array1));
    size_t index1 = 0, index2 = 0;
    size_t i;


    for(i = 0; i < size1 + size2 && index1 < size1 && index2 < size2; i++)
    {   
        if(asc)
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
        else
        {
            if(array1[index1] > array2[index2]) result[i] = array2[index2++];
            else result[i] = array1[index1++];
        }
    }
    if(index1 == size1) memcpy(result + i, array2 + index2, sizeof(result) * (size2 - index2));
    if(index2 == size2) memcpy(result + i, array1 + index1, sizeof(result) * (size1 - index1));
    return result;
}

int main(void)
{
    srand(time(NULL));
    size_t size1 = rand() % 20, size2 = rand() % 20;
    int *mergedArray;

    if(size1 < 5) size1 += 5;
    if(size2 < 5) size2 += 5;

    int array1[size1], array2[size2];

    for(size_t i = 0; i < size1; i++)
        array1[i] = rand();
    for(size_t i = 0; i < size2; i++) 
        array2[i] = rand();
    sort(array1, size1);
    sort(array2, size2);

    for(size_t i = 0; i < size1; i++)
        printf("array1[%2zu] = %d\n", i, array1[i]);
    for(size_t i = 0; i < size2; i++)
        printf("array2[%2zu] = %d\n", i, array2[i]);

    mergedArray = mergeArrays(array1, array2, size1, size2, 1);
    for(size_t i = 0; i < size2 + size1; i++)
        printf("result[%2zu] = %d\n", i, mergedArray[i]);
}

你需要添加内存分配检查，空指针检查等。

Answer 2

您的任务是实现合并排序算法的合并阶段。mergesort 对数据集进行排序的复杂性为 O（N.log（N）），但每个合并阶段都需要与合并集长度成正比的线性时间。

这是用于此的伪代码：

merge(array a, array b into array c)
    int i = 0, j = 0, k = 0;
    while (i < len(a) and j < len(b)) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < len(a)) {
        c[k++] = a[i++];
    }
    while (j < len(b)) {
        c[k++] = b[j++];
    }
}

复杂度是线性的，因为每个循环中的每个步骤都将一个元素复制到c数组中，总共len（a）len（b）步骤。