程序填空题：归并排序
归并排序。
```c++
#include
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
if(i==1)
cout< else
cout<<" "<}
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=low;
while(@@[i<=mid&&j<=high](2))
{
if(@@[R[i].key<=R[j].key](2)) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(@@[i<=mid](2))
T[k++]=R[i++];
while(@@[j<=high](2))
T[k++]=R[j++];
}
void MSort(RedType R[],RedType T[],int low,int high)
{
int mid;
RedType *S=new RedType[MAXSIZE];
if(low==high)@@[T[low]=R[low]](2);
else
{
mid=(low+high)/2;
@@[MSort(R,S,low,mid)](2);
@@[MSort(R,S,mid+1,high)](2);
Merge(S,T,low,mid,high);
}
}
void MergeSort(SqList &L)
{
MSort(L.r,L.r,1,L.length);
}
int main()
{
SqList R;
R.r=new RedType[MAXSIZE+1];
R.length=0;
Create_Sq(R);
MergeSort(R);
show(R);
return 0;
}
```
### 输入样例：
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
```in
7
24 53 45 45 12 24 90
```
### 输出样例：
输出排序结果。
```out
12 24 24 45 45 53 90
```
答案：
第1空：i<=mid&&j<=high
第2空：R[i].key<=R[j].key
第3空：i<=mid
第4空：j<=high
第5空：T[low]=R[low]
第6空：MSort(R,S,low,mid)
第7空：MSort(R,S,mid+1,high)
```c++
#include
#define MAXSIZE 1000
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
if(i==1)
cout<
cout<<" "<
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
int i,j,k;
i=low; j=mid+1;k=low;
while(@@[i<=mid&&j<=high](2))
{
if(@@[R[i].key<=R[j].key](2)) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(@@[i<=mid](2))
T[k++]=R[i++];
while(@@[j<=high](2))
T[k++]=R[j++];
}
void MSort(RedType R[],RedType T[],int low,int high)
{
int mid;
RedType *S=new RedType[MAXSIZE];
if(low==high)@@[T[low]=R[low]](2);
else
{
mid=(low+high)/2;
@@[MSort(R,S,low,mid)](2);
@@[MSort(R,S,mid+1,high)](2);
Merge(S,T,low,mid,high);
}
}
void MergeSort(SqList &L)
{
MSort(L.r,L.r,1,L.length);
}
int main()
{
SqList R;
R.r=new RedType[MAXSIZE+1];
R.length=0;
Create_Sq(R);
MergeSort(R);
show(R);
return 0;
}
```
### 输入样例：
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
```in
7
24 53 45 45 12 24 90
```
### 输出样例：
输出排序结果。
```out
12 24 24 45 45 53 90
```
答案：
第1空：i<=mid&&j<=high
第2空：R[i].key<=R[j].key
第3空：i<=mid
第4空：j<=high
第5空：T[low]=R[low]
第6空：MSort(R,S,low,mid)
第7空：MSort(R,S,mid+1,high)
