21xrx.com
2024-11-22 09:51:12 Friday
登录
文章检索 我的文章 写文章
C++合并排序实现从小到大排序代码
2023-07-09 04:57:46 深夜i     --     --
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++代码,我们可以非常方便地实现对数组的从小到大排序,应用找到场景,与大家分享。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复