C++顺序表实现归并排序算法代码 |21xrx.com

C++顺序表实现归并排序算法代码

2023-07-05 10:17:19 深夜i -- --

C++ 顺序表归并排序算法实现代码

归并排序是计算机科学中一种高效的排序算法。在这个算法中，原始数据会被不断地划分成更小的部分，然后这些部分会被逐一合并成一个有序的序列，从而获得最终的排序结果。这个算法通常被认为是一种分治算法，因为它将排序问题分解成了更小的子问题来解决。

在C++中，我们可以使用顺序表来实现归并排序算法。顺序表是一种基于数组的数据结构，可以用于存储一系列有序的元素，并支持快速查询、插入和删除等操作。在此基础上，我们可以将归并排序算法拆解成三个关键步骤：分割数组、合并数组和排序数组。

下面是C++顺序表实现归并排序算法的代码：


#include <iostream>
#include <vector>
#include <algorithm>
template <class T>
void merge(std::vector<T>& arr, int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;
  std::vector<T> left(n1);
  std::vector<T> right(n2);
  for (int i = 0; i < n1; i++) {
    left[i] = arr[l + i];
  }
  for (int j = 0; j < n2; j++) {
    right[j] = arr[m + 1 + j];
  }
  int i = 0, j = 0, k = l;
  while (i < n1 && j < n2) {
    if (left[i] <= right[j]) {
      arr[k] = left[i];
      i++;
    }
    else {
      arr[k] = right[j];
      j++;
    }
    k++;
  }
  while (i < n1) {
    arr[k] = left[i];
    i++;
    k++;
  }
  while (j < n2) {
    arr[k] = right[j];
    j++;
    k++;
  }
}
template <class T>
void mergeSort(std::vector<T>& 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 = 1;
  mergeSort(arr, 0, arr.size() - 1);
  for (int i = 0; i < arr.size(); i++) {
    std::cout << arr[i] << " ";
  }
  return 0;
}

以上代码首先定义了一个merge模板函数，用于合并两个已经排序好的数组。这个函数会先将数组拆分成左右两个子数组，然后逐一比较这两个子数组的元素，按照顺序合并到一个新的数组中。具体来说，这个函数会首先初始化两个空的vector对象，然后将原始数组中左右两方划分成的子数组分别存入这两个对象中。接下来，我们使用三个指针i、j、k来遍历这三个数组，并依次进行比较和合并操作，直到所有元素都被处理完毕。

接着我们实现了一个mergeSort模板函数，用于对整个数组进行归并排序操作。这个函数是一个递归函数，先将原始数组划分成两部分（从中间分割），并对左半部分和右半部分分别调用mergeSort函数，直到最终只剩下单个元素。然后通过调用merge函数，将左右两个已经排序好的子数组进行合并，得到有序的最终结果。

最后我们在main函数中定义了一个vector类型的数组arr，然后调用mergeSort函数对它进行排序，输出排序结果即可。

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

下一篇: 如何在C++中设置控制台窗口大小

评论区

()

相似文章