C++归并排序算法实现 |21xrx.com

C++归并排序算法实现

2023-07-01 08:46:38 深夜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);
  }
}

其中`mergeSort`函数是归并排序的主要函数，它使用递归的方式将数组不断划分为更小的子数组并排序。`merge`函数则用来合并两个已排好序的子数组。

当然，以上的C++归并排序算法实现仅作为一个简单的示例，可能还有更好的优化和改进方法。但相信通过对这个例子进行深入学习和实践后，程序员们可以更好地理解C++中归并排序的实现方式，并在实际应用中取得更好的效果。

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

下一篇: 如何在Dev-C++中修改字体？

评论区

()

相似文章