C++数组合并排序 |21xrx.com

C++数组合并排序

2023-06-22 01:30:45 深夜i -- --

C++ Arrays Merge Sorting

C++是一种广泛使用的编程语言，提供了强大的数组操作能力。其中，数组合并排序是常见的操作之一。在这篇文章中，我们将介绍如何使用C++来完成数组合并排序的操作。

首先，我们需要了解一下C++中数组的定义和使用。在C++中，数组是一组相同类型的数据的有序集合，可以通过下标进行访问。例如，以下代码定义了一个包含5个整数的数组并对其进行初始化：


int arr[5] = 1;

接下来，我们需要将两个数组进行合并。假设我们有两个数组a和b，它们的元素个数分别为n和m。我们可以使用一个新的数组c来存储合并后的结果，如下所示：


int c[n+m];
for (int i=0; i<n; i++) {
  c[i] = a[i];
}
for (int i=0; i<m; i++) {
  c[n+i] = b[i];
}

在上面的代码中，我们首先定义了一个新的数组c，长度为n+m。然后，我们使用两个for循环将数组a和数组b的元素依次复制到数组c中。其中，第一个循环是从0到n-1遍历数组a，将元素复制到c[i]中；第二个循环是从0到m-1遍历数组b，将元素复制到c[n+i]中。最终，我们得到了一个长度为n+m的新数组c，其中包含了数组a和数组b的所有元素。

接下来，我们需要对数组c进行排序。C++提供了多种排序算法，例如冒泡排序、快速排序、归并排序等。在这里，我们选择使用归并排序。归并排序的基本思想是将数组分成两部分进行排序，然后将两部分合并起来。具体实现如下：


void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    merge(arr, l, mid, r);
  }
}
void merge(int arr[], int l, int mid, int r) {
  int n1 = mid - l + 1, n2 = r - mid;
  int L[n1], R[n2];
  for (int i=0; i<n1; i++) {
    L[i] = arr[l+i];
  }
  for (int j=0; j<n2; j++) {
    R[j] = arr[mid+1+j];
  }
  int 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++;
  }
}

在上面的代码中，我们定义了两个函数：mergeSort和merge。mergeSort函数用来分别排序左半部分和右半部分，最后将两部分合并起来；merge函数用来将两个有序数组合并成一个有序数组。具体而言，merge函数首先定义了两个数组L和R，将原数组a分成左半部分和右半部分。然后，它使用了三个指针，分别指向数组L、数组R和原数组a的当前位置。循环比较L[i]和R[j]的大小，并将较小的元素存放到原数组a的当前位置，最后将指针i、j、k分别增加，直到将L和R中的所有元素都归并到原数组a中。

最终，我们可以将合并后的数组c进行归并排序的操作，如下所示：


mergeSort(c, 0, n+m-1);

这行代码调用了我们之前定义的mergeSort函数，将数组c进行归并排序。其中，第一个参数是待排序的数组c，第二个参数是数组左侧的下标l，第三个参数是数组右侧的下标r。

综上所述，使用C++实现数组合并排序的过程包括三个步骤：定义新数组、将两个数组合并到新数组中、对新数组进行归并排序。C++提供了丰富的数组操作能力和多种排序算法，可以帮助我们方便快捷地完成数组合并排序的操作。

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

下一篇: C++ Auto用法详解

评论区

()

相似文章