【算法】合并排序的递归实现算法
基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
合并排序的递归实现算法。
输入：先输入进行合并排序元素的个数，然后依次随机输入（或随机生成）每个数字。
输出：元素排序后的结果，数字之间不加任何标识符。
示例：输入：8 11 1 2 4 8 6 15 8，输出：1 2 4 6 8 8 11 15
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int b[maxn];
void merge(int a[],int left,int mid,int right){//merge可在O(n)时间内完成
int i=left,j=mid+1;
int k=left;
while(i<=mid&&j<=right){
if(a[i]>=a[j])b[k++]=a[j++];
else b[k++]=a[i++];
}
//比完了之后剩余的依次存下
if(i>mid)for(int q=k;q<=right;q++)b[k++]=a[j++];
else for(int q=k;q<=right;q++)b[k++]=a[i++];
//将合并后的数组段再复制回数组a中
for(int i=left;i<=right;i++)a[i]=b[i];
}
void sort(int a[],int left,int right){
if (left<right){//至少有2个元素
int mid=(left+right)/2;//取中点
sort(a,left,mid);
sort(a,mid+1,right);
merge(a,left,mid,right);//合并两个排好序的数组段到一个新的
}
}
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
sort(a,0,n-1);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
，
查看19道真题和解析