21xrx.com
2024-11-22 07:10:00 Friday
登录
文章检索 我的文章 写文章
C++实现归并算法合并两个有序数组
2023-07-11 15:06:04 深夜i     --     --
C++ 归并算法 有序数组 合并

归并算法是一种常见的排序算法,在计算机科学中广泛应用。归并算法的主要思想是将一个大文件分割成若干个更小的文件,然后将这些小文件进行排序并归并成一个有序的大文件。

在C++语言中,利用归并算法合并两个有序数组比较简单。下面我们来看一下具体的实现过程。

首先,我们需要定义两个有序数组。假设两个数组分别为arr1和arr2,它们都是从小到大排序的。创建一个新的数组arr3,用于存放合并后的结果。

接下来,我们定义三个变量i、j和k,分别用于指向arr1、arr2和arr3的某个元素。初始化i和j为0,表示从数组的第一个元素开始合并。变量k为0,表示从数组的第一个位置开始存储合并后的结果。

然后,我们循环比较arr1和arr2的元素大小,将较小的元素存储在arr3中,并将i或j的值加1。同时,k的值也加1,表示下一个元素存储的位置。

如果arr1或arr2中有一个数组的所有元素都已经比较完毕,那么我们直接将剩余的元素添加到arr3的末尾即可。

最后,arr3就是合并后的有序数组,可以输出结果。

以下是代码示例:


#include<iostream>

using namespace std;

int main()

{

  int arr1[] = 5;

  int arr2[] = 10;

  int n1 = sizeof(arr1) / sizeof(int);

  int n2 = sizeof(arr2) / sizeof(int);

  int arr3[100];

  int i = 0, j = 0, k = 0;

  while(i < n1 && j < n2)

  {

    if(arr1[i] <= arr2[j])

    {

      arr3[k++] = arr1[i++];

    }

    else

    {

      arr3[k++] = arr2[j++];

    }

  }

  while(i < n1)

  {

    arr3[k++] = arr1[i++];

  }

  while(j < n2)

  {

    arr3[k++] = arr2[j++];

  }

  for(int p = 0; p < k; p++)

  {

    cout << arr3[p] << " ";

  }

  return 0;

}

上述代码中,我们通过while循环遍历arr1和arr2的元素,并将较小的元素添加到arr3中。如果arr1或arr2中有剩余的元素,我们可以通过两个单独的while循环将它们添加到arr3的末尾。

最后,我们输出合并后的有序数组。

通过以上步骤,我们就成功使用C++实现了归并算法合并两个有序数组。在实际开发中,我们可以根据具体的需求对此进行改进或优化,使算法更加高效。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复