C++合并排序实现从小到大排序代码 |21xrx.com

C++合并排序实现从小到大排序代码

2023-07-09 04:57:46 深夜i 10 0

C++ 合并排序从小到大排序代码

C++是一种非常常用的编程语言，它可以被用于实现各种算法。其中，合并排序是一种比较常见的排序算法，它可以实现从小到大的排序。下面，本文将介绍如何使用C++编写合并排序算法的代码，并实现从小到大排序。

合并排序算法的基本思想是分治法，即将一个大问题分解成若干个小问题，再将小问题解决后合并成整体的解决方案。具体来说，合并排序将要排序的数组递归地分解为两个子数组，然后对两个子数组分别进行排序，最后将两个子数组合并为一个有序数组。

现在，让我们看看如何使用C++实现合并排序算法的代码：

#include<iostream>
using namespace std;
void merge(int a[], int p, int q, int r){
  int i,j,k,n1,n2;
  n1=q-p+1; //计算左半部分元素个数n1
  n2=r-q;  //计算右半部分元素个数n2
  int L[n1+1],R[n2+1]; //定义新的左右数组
  for(i=1;i<=n1;i++){
    L[i]=a[p+i-1];
  }
  for(j=1;j<=n2;j++){
    R[j]=a[q+j];
  }
  L[n1+1]=100000; //定义左部数组哨兵
  R[n2+1]=100000; //定义右部数组哨兵
  i=1;
  j=1;
  for(k=p;k<=r;k++){
    if(L[i]<=R[j]){
      a[k]=L[i];
      i++;
    }
    else{
      a[k]=R[j];
      j++;
    }
  }
}
void merge_sort(int a[], int p, int r){
  int q=0;
  if(p<r){
    q=(p+r)/2;
    merge_sort(a,p,q); //递归排序左半部分
    merge_sort(a,q+1,r); //递归排序右半部分
    merge(a,p,q,r); //归并左右两个有序数组
  }
}
int main(){
  int n;  //输入元素的个数
  cin>>n;
  int a[n+1];
  for(int i=1;i<=n;i++){  //输入n个数，存入数组a中
    cin>>a[i];
  }
  merge_sort(a,1,n); //排序
  for(int i=1;i<=n;i++){ //输出排序后的数列
    cout<<a[i]<<" ";
  }
  return 0;
}

以上就是合并排序算法的C++实现代码。代码中，merge函数用于归并两个有序数组，merge_sort函数则实现了递归调用和两个有序数组的合并操作。最后，main函数用于输入、排序和输出数组元素。

使用上述C++代码，我们可以非常方便地实现对数组的从小到大排序，应用找到场景，与大家分享。

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

下一篇: C++中构造函数调用构造函数的方式

评论区

相似文章