使用for循环合并两个排序数组

Question

我有一个函数可以将两个排序的数组合并为一个，returns 一个指向它的指针。我想使用 for 循环而不是一段时间。但是，在某些测试用例中，合并数组的最后 1 或 2 个元素不在其位置。如果有人可以帮助解决这个保持 for 循环的问题，我将不胜感激。

int * mergeSort(int arr1[], int arr2[],int len)
{

  /* len is the combined length of the two arrays */

    static int sorted[100];

    int pos1=0, pos2=0;

    for (int i=0; i<len; i++)
    {
        if (arr1[pos1]<=arr2[pos2])
        {
            sorted[i]=arr1[pos1];
            pos1++;
        }
        else
        {
            sorted[i]=arr2[pos2];
            pos2++;
        }
    }

    return sorted;
}

Answer 1

您的问题是您似乎无法处理超出输入数组末尾的问题。如果有未初始化的内存 - 你会得到未定义的行为。

您可以通过使用标记值终止数组来避免这种情况，例如 INT_MAX，它应该始终大于数组中所有可能的值：

int a[] = { 1, 2, 104, INT_MAX};
int b[] = { 101, 102, 105, INT_MAX};

int* ptr = mergeSort(a,b,6);

for(int i = 0; i < 6; i++){
    cout << i << " " << ptr[i] << endl;
}

live demo

或者您可以传递两个数组的实际长度并正确处理它们：

int * mergeSort(int arr1[], int len1, int arr2[],int len2)
{

  /* len is the combined length of the two arrays */

    static int sorted[100];

    int pos1=0, pos2=0;

    for (int i=0; i< len1 + len2; i++)
    {
        if ((pos2 == len2) || (arr1[pos1] <= arr2[pos2] && (pos1 < len1)))
        {
            sorted[i]=arr1[pos1];
            pos1++;
        }
        else
        {
            sorted[i]=arr2[pos2];
            pos2++;
        }
    }

    return sorted;
}

live demo

Answer 2

这并没有回答您的代码有什么问题，但是为了回答如何合并两个排序范围的问题，我建议 std::merge:

    int * mergeSort(int arr1[], int arr2[], int len1, int len2)
    {
        //I am not condoning the use of a static buffer here,
        //I would probably use a std::vector or std::array,
        //possibly a boost::static_vector if really necessary
        static int sorted[100];
        std::merge(arr1, arr1 + len1, arr2, arr2 + len2, sorted);
        return sorted;
    }

我还将 int len 更改为 int len1, int len2，因为您需要知道各个数组的长度，而不仅仅是它们的组合长度，以避免读取超过输入数组的末尾。

使用for循环合并两个排序数组

Merging two sorted arrays with for loop

c++

arrays

array-merge