C++语言实现归并排序 |21xrx.com

C++语言实现归并排序

2023-06-26 18:38:34 深夜i -- --

C++ 归并排序实现

归并排序是一种效率高且稳定的排序算法，它是采用分治策略的典型实现。C++语言是一种高效而强大的编程语言，为实现归并排序提供了便捷的工具。

归并排序的基本思想是将待排序数组分为两个部分，然后对这两个部分进行排序，最后将它们合并成一个有序数组。在归并排序中，利用递归的方式对分割出来的小数组进行排序，确保最终的数组是有序的。

在C++中，实现归并排序可以借助STL中的vector容器，利用其对数组的封装，从而直接对vector进行排序。代码如下：


#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int start, int mid, int end){
  int left = start;
  int right = mid + 1;
  vector<int> tmp;
  while (left <= mid && right <= end) {
    if (arr[left] <= arr[right])
      tmp.push_back(arr[left++]);
    else
      tmp.push_back(arr[right++]);
  }
  while (left <= mid)
    tmp.push_back(arr[left++]);
  while (right <= end)
    tmp.push_back(arr[right++]);
  for (int i = 0; i < tmp.size(); i++){
    arr[start + i] = tmp[i];
  }
}
void merge_sort(vector<int>& arr, int start, int end){
  if (start >= end)
    return;
  int mid = (start + end) / 2;
  merge_sort(arr, start, mid);
  merge_sort(arr, mid + 1, end);
  merge(arr, start, mid, end);
}
int main(){
  vector<int> arr = 3;
  merge_sort(arr, 0, arr.size() - 1);
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

在这个代码中，我们通过调用merge_sort()函数对待排序数组进行排序。该函数采用类似于二分查找的方法将数组分割成两部分，并递归地对子数组进行排序。最后，我们将两个排序后的子数组合并成一个有序数组，并交换元素的位置。

归并排序是一种高效、可靠且易于实现的算法，是C++程序员的必备技能之一。通过掌握归并排序的实现方法，可以提高自己的算法、编程能力。

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

下一篇: C语言与C++的数据结构的比较

评论区

()

相似文章