建设银行青海省分行招聘网站dux2.0支持Wordpress
6-2 归并排序
分数 10
全屏浏览
切换布局
作者 软件工程DS&A课程组
单位 燕山大学
以下代码采用分而治之算法实现归并排序。请补充函数mergesort（）的代码。提示：mergesort（）函数可用递归实现，其中参数n在递归调用中不需要变化。
函数接口定义：
void mergesort(int a[],int n,int left,int right)；其中a[], n ,left和 right 都是用户传入的参数。 `
裁判测试程序样例：
#include<iostream>
using namespace std;
const int maxn=500000,INF=0x3f3f3f3f;
int L[maxn/2+2],R[maxn/2+2];
void merge(int a[],int n,int left,int mid,int right)
{int n1=mid-left,n2=right-mid;for(int i=0;i<n1;i++)L[i]=a[left+i];for(int i=0;i<n2;i++)R[i]=a[mid+i];L[n1]=R[n2]=INF;int i=0,j=0;for(int k=left;k<right;k++){if(L[i]<=R[j])a[k]=L[i++];elsea[k]=R[j++];}
}
void mergesort(int a[],int n,int left,int right)
{}
int main()
{int a[maxn],n;cin>>n;for(int i=0;i<n;i++)cin>>a[i];mergesort(a,n,0,n);for(int i=0;i<n;i++){if(i)cout<<" ";cout<<a[i];}cout<<endl;return 0;
}
输入样例：
10
23 -8 45 6 17 5 998 30 26 77
输出样例：
-8 5 6 17 23 26 30 45 77 998
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
代码分享：
for(int i=left;i<right;i++){for(int j=i;j<right;j++){if(a[j]<a[i]){int temp=a[i];a[i]=a[j];a[j]=temp;}}}