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

C++实现合并排序算法

2023-07-10 02:28:28 深夜i 17 0

C++ 合并排序算法排序递归

合并排序（Merge Sort）是一种基于分治策略的排序算法，通过将待排序元素序列分成两个部分，对这两个部分分别排序，最后将排序后的结果合并起来得到有序的序列。在这个过程中，使用了归并（Merge）操作来将排序好的序列合并。

C++语言提供了丰富的功能和工具，可以非常方便地实现合并排序算法。下面是一段基于C++实现的合并排序的代码：

#include <iostream>
#include <vector>
// Merge function
void merge(std::vector<int>& arr, int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;
  std::vector<int> L(n1);
  std::vector<int> R(n2);
  for (int i = 0; i < n1; i++) {
    L[i] = arr[l + i];
  }
  for (int j = 0; j < n2; j++) {
    R[j] = arr[m + 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++;
  }
}
// Merge Sort function
void mergeSort(std::vector<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);
  }
}
int main() {
  std::vector<int> arr = 7 ;
  int n = arr.size();
  mergeSort(arr, 0, n - 1);
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}

在这个代码中，merge()函数实现了归并操作，将两个已排序的序列合并成一个。mergeSort()函数使用递归的方式，将待排序元素序列不断划分为两个子序列，直到每个子序列包含一个元素。然后，将两个子序列合并起来，得到排好序的序列。

通过使用C++ STL库中的vector容器，代码实现非常简单，可读性也很高。这个合并排序算法的时间复杂度为O(nlogn)，空间复杂度为O(n)，是一种非常高效的排序算法。

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

下一篇: C++ 薪资水平

评论区

相似文章