C++实现两个有序数组合并成一个有序数组 |21xrx.com

C++实现两个有序数组合并成一个有序数组

2023-07-09 14:40:53 深夜i -- --

C++ 有序数组合并

C++作为一门高级编程语言，可以实现很多复杂的功能，包括将两个有序数组合并成一个有序数组。在本文中，我们将介绍如何使用C++程序实现这一功能。

首先，我们需要明确两个有序数组需要满足的条件。这两个数组必须是有序的，即数组中的元素从小到大排列。否则，在合并两个数组时会导致结果混乱。因此，在实现时我们需要先将两个数组排序。

C++中提供了很多排序算法，例如冒泡排序、插入排序、快速排序和归并排序等。在这里，我们可以选择归并排序作为我们的排序算法。下面是一个归并排序的实现代码。


void merge(int arr[], int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];
  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  i = 0;
  j = 0;
  k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}

接下来，我们需要实现将两个有序数组合并的功能。假设我们有两个有序数组arr1和arr2，它们的长度分别为n1和n2。我们可以定义一个新的数组arr3，来存储合并后的结果。由于arr1和arr2都是有序的，我们可以依次比较它们的元素，并将较小的元素放入arr3中，直到两个数组中的元素都被遍历过。下面是合并两个数组的实现代码。


void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[])
{
  int i = 0, j = 0, k = 0;
  // Traverse both arrays
  while (i < n1 && j < n2) {
    // Check if current element of first
    // array is smaller than current element
    // of second array. If yes, store first
    // array element and increment first array
    // index. Otherwise do same with second array
    if (arr1[i] < arr2[j])
      arr3[k++] = arr1[i++];
    else
      arr3[k++] = arr2[j++];
  }
  // Store remaining elements of first array
  while (i < n1)
    arr3[k++] = arr1[i++];
  // Store remaining elements of second array
  while (j < n2)
    arr3[k++] = arr2[j++];
}

现在我们已经定义了归并排序和合并两个有序数组的功能。接下来，我们可以将这两个功能结合起来，实现将两个有序数组合并成一个有序数组的功能。


void mergeSortedArrays(int arr1[], int arr2[], int n1,
            int n2, int arr3[])
{
  // Sort both arrays
  mergeSort(arr1, 0, n1 - 1);
  mergeSort(arr2, 0, n2 - 1);
  // Merge sorted arrays
  mergeArrays(arr1, arr2, n1, n2, arr3);
}

最后，我们可以在主程序中调用mergeSortedArrays函数，将两个有序数组合并成一个有序数组。下面是一个完整的程序示例。


#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1], R[n2];
  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];
  i = 0;
  j = 0;
  k = l;
  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}
void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[])
{
  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++];
}
void mergeSortedArrays(int arr1[], int arr2[], int n1,
            int n2, int arr3[])
{
  mergeSort(arr1, 0, n1 - 1);
  mergeSort(arr2, 0, n2 - 1);
  mergeArrays(arr1, arr2, n1, n2, arr3);
}
int main()
{
  int arr1[] = 7;
  int arr2[] = 8 ;
  int n1 = sizeof(arr1) / sizeof(arr1[0]);
  int n2 = sizeof(arr2) / sizeof(arr2[0]);
  int arr3[n1 + n2];
  mergeSortedArrays(arr1, arr2, n1, n2, arr3);
  cout << "Merged array is: ";
  for (int i = 0; i < n1 + n2; i++)
    cout << arr3[i] << " ";
  return 0;
}

运行结果为：

Merged array is: 1 2 3 4 5 6 7 8 9

到这里，我们已经成功地将两个有序数组合并成一个有序数组。通过学习这个例子，我们可以看到，C++这门高级编程语言的强大之处，在于它可以实现很多复杂的功能，只要我们使用好它提供的相关函数和工具库，就可以轻松实现所需的功能。

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

下一篇: C++中的vector源码分析：了解分配器的实现原理

评论区

()

相似文章