归并排序（包括完整代码）

归并排序（包括完整代码）

引用

CSDN

1.

https://blog.csdn.net/Chenqin1879/article/details/140875935

归并排序是一种采用分治策略进行排序的算法，而分治的本质是将一个大规模的问题分解为若干规模较小的相同子问题，分而治之。
由于排序问题给定的是一个无序序列，所以可以把待排序元素分解成两个规模大致相等的子序列，如果不易解决，则将得到的子序列继续分解，直到子序列包含的元素个数为1（因为单个元素的序列本身就是有序的），此时就可以进行合并，从而得到一个完整的有序序列。以序列（42，15，20，6，8，38，50，12）为例：

从上图可以看出，首先将待排序元素分成大小大致相同的两个子序列，然后把子序列分成两个大小大致相同的两个子序列，如此下去，直到分解成一个元素时为止，这时含有一个元素的子序列就是有序的。然后再执行合并操作，将两个有序的子序列合并成一个有序序列，如此下去，制直到所有的元素都合并为一个有序序列时为止。

具体代码如下：

#include<bits/stdc++.h>
using namespace std; 
void he(int A[],int low,int mid,int high){
    int *B=new int[high-low+1];//申请一个动态数组进行辅助 
    int i=low,j=mid+1,k=0;
    while(i<=mid&&j<=high){//按从小到大的顺序放入辅助数组中 
        if(A[i]<=A[j])
            B[k++]=A[i++];
        else
            B[k++]=A[j++];
    }
    while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放入辅助数组中 
    while(j<=high) B[k++]=A[j++];
    for(i=low,k=0;i<=high;i++,k++){//将排序好的辅助数组复制到原数组中 
        A[i]=B[k];
    } 
    delete[] B;//释放内存空间 
}
void fen(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;//取中点 
        fen(A,low,mid);//对A[low：mid]中的元素合并排序 
        fen(A,mid+1,high);//对A[mid+1:high]中的元素合并排序 
        he(A,low,mid,high);//合并 
    }
}
int main(){
    int a[1005];
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
   fen(a,0,n-1);//调用函数
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
}