C++编程实现有序数组合并 |21xrx.com

C++编程实现有序数组合并

2023-07-07 22:11:53 深夜i -- --

C++编程有序数组合并

在C++编程中，有序数组合并是一项非常基础但又十分常见的技能。当我们处理多个有序数组时，有时需要把它们合并成一个新的有序数组。这个过程可以通过使用归并排序算法来实现。下面，我们将介绍如何在C++中实现有序数组合并。

1. 归并排序算法简介

归并排序算法是一种分治法的算法，它将一个大问题拆分为若干个子问题，解决子问题后再将结果合并为一个整体。其主要步骤如下：

（1）将待排序的序列从中间位置分成两个子序列；

（2）对两个子序列分别进行归并排序；

（3）将两个已经有序的子序列合并成一个整体有序序列，直到排序完成。

2. 实现步骤

（1）定义两个指针i和j，分别指向待合并的两个有序数组的起始位置；

（2）创建一个新的有序数组，用于存储合并后的有序数组；

（3）从两个有序数组中取出第一个元素进行比较，将较小的元素放到新的数组中，并将指针向后移动一个位置；

（4）重复第三步，直到任一一个有序数组的元素全部放入新的数组中；

（5）将另一个有序数组中剩余的元素全部放入新的数组中。

下面是一个示例代码：


#include <iostream>
using namespace std;
void merge(int a[], int start, int mid, int end)
{
  int* tmp = new int[end - start + 1];
  int i = start, j = mid + 1, k = 0;
  while (i <= mid && j <= end)
  {
    tmp[k++] = (a[i] < a[j]) ? a[i++] : a[j++];
  }
  while (i <= mid)
  {
    tmp[k++] = a[i++];
  }
  while (j <= end)
  {
    tmp[k++] = a[j++];
  }
  for (i = start, k = 0; i <= end; ++i, ++k)
  {
    a[i] = tmp[k];
  }
  delete[] tmp; 
}
void mergeSort(int a[], int start, int end)
{
  if (start < end)
  {
    int mid = (start + end) / 2;
    mergeSort(a, start, mid);
    mergeSort(a, mid + 1, end);
    merge(a, start, mid, end);
  }
}
int* mergeArrays(int a[], int b[], int n, int m)
{
  int* result = new int[n + m];
  int i = 0, j = 0, k = 0;
  while (i < n && j < m)
  {
    if (a[i] < b[j])
    {
      result[k++] = a[i++];
    }
    else if (a[i] > b[j])
    {
      result[k++] = b[j++];
    }
    else
    {
      result[k++] = a[i++];
      result[k++] = b[j++];
    }
  }
  while (i < n)
  {
    result[k++] = a[i++];
  }
  while (j < m)
  {
    result[k++] = b[j++];
  }
  return result;
}
int main()
{
  int a[] = 3;
  int b[] = 2;
  int n = sizeof(a) / sizeof(a[0]);
  int m = sizeof(b) / sizeof(b[0]);
  mergeSort(a, 0, n - 1);
  mergeSort(b, 0, m - 1);
  int* result = mergeArrays(a, b, n, m);
  for (int i = 0; i < n + m; ++i)
  {
    cout << result[i] << " ";
  }
  delete[] result;
  return 0;
}

在上面的代码中，我们首先调用了mergeSort()函数对两个有序数组进行排序，然后调用了mergeArrays()函数将两个数组合并成一个新的有序数组。

3. 总结

在本文中，我们介绍了如何在C++编程中使用归并排序算法实现有序数组合并的过程。通过掌握这一基本技能，我们可以更加高效地处理多个有序数组的合并操作，提高程序的执行效率。希望本文对您有所帮助！

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

下一篇: C++编写头文件的方法及规范

评论区

()

相似文章