C++合并排序代码 |21xrx.com

C++合并排序代码

2023-06-22 04:57:16 深夜i -- --

C++ 合并排序代码

合并排序是一种经典的排序算法，它采用分治策略，将一个待排数组不断划分成两个规模较小的子数组，直至每个子数组只含一个或零个元素，然后采用两个已排好序的子数组进行归并，最终得到一个有序的数组。C++语言是一门常用的编程语言，本文将给出C++实现合并排序的代码。

首先，我们需要定义一个函数merge()，这个函数用于将两个有序数组合并成一个有序数组。代码如下：


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++;
  }
}

上述代码的作用就是将一个待排数组的左部分[l, m]和右部分[m+1, r]合并成一个有序数组，其中l,m,r都是数组索引。

接下来，我们定义一个函数mergeSort()，这个函数用于将待排数组不断划分成子数组，直至每个子数组只含一个或零个元素，然后采用merge()函数进行归并。代码如下：


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);
  }
}

上述代码的作用就是将待排数组的左部分[l, m]和右部分[m+1, r]分别进行递归，直到最后只有一个或者零个元素，然后采用merge()函数将两个子数组合并成一个有序数组。

最后，我们编写一个主函数，用来测试上述两个函数的效果。主函数的代码如下：


int main() {
  int arr[] = 6;
  int arr_size = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, arr_size - 1);
  cout << "Sorted array: \n";
  for (int i = 0; i < arr_size; i++)
    cout << arr[i] << " ";
  cout << endl;
  return 0;
}

主函数的作用是定义一个待排数组，然后传入mergeSort()函数进行排序，最后输出排序后的有序数组。

综上所述，我们使用C++实现了合并排序算法，并进行了简单的测试，代码简洁可读，是一种常见的排序算法之一。

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

下一篇: 如何解决Visual C++2010安装组件失败问题

评论区

()

相似文章