C++实现归并算法合并两个有序数组 |21xrx.com

C++实现归并算法合并两个有序数组

2023-07-11 15:06:04 深夜i 29 0

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++实现了归并算法合并两个有序数组。在实际开发中，我们可以根据具体的需求对此进行改进或优化，使算法更加高效。

上一篇: idea打包java可执行jar包

下一篇: C++递归：猴子吃桃子

评论区

相似文章