问题及代码：
2756: C++习题-归并排序
Time Limit: 1 Sec
Memory Limit: 128 MB
Submit: 73
Solved: 53
[
Submit][
Status][
Web Board]
Description
有数列{6 58 14 2 19 354 684 4} （1）申请一个数组q，准备存放合并后的序列 （2）将原序列拆分为左序列{6 58 14 2}与右序列{19 354 68 4} （3）将左右数组分别有序排列成{2 6 14 58}及{4 19 68 354} [这一过程通过递归重复（2）～（7）实现] （4）设定i，j分别为两序列的初始位置 （5）比较i，j位置对应元素大小，选择小的放入数组q，同时将i或j加1 （6）重复步骤（5）直到i或j中有一个达到序列尾 （7）最后将剩余的元素复制到数组q中，两子序列就合并为一个有序序列了 注：本题只需提交部分代码,输入n(n<=100)及n个整数,输出按从小到大顺序排列好的数据 #include <iostream> using namespace std; void MergeSort(int p[],int s,int m,int t) { int q[100]; //临时数组q[100]用来存放排好的序列 int i,j,k; //i作为左数组起始位置,j作为右数组起始位置,k为临时数组位置 for (i=s,j=m+1,k=0; k<=t-s; k++) { if (i==m+1) //当i到达左数组的最后时,将右数组余下元素复制到临时数组中 { q[k]=p[j]; j++; continue; } if (j==t+1) //当j达到右数组最后时,将左数组剩余元素复制到临时数组中 { q[k]=p[i];
i++; continue; }
/// /* 请在该部分填写缺少的代码 */
} for(i=s,j=0; i<=t; i++,j++) //将临时数组的对应各项值赋给数组p[100] p[i]=q[j];
} void Merge(int p[],int s,int t) { if(s<t) { int m=(s+t)/2; Merge(p,s,m); //递归对左数组进行归并 Merge(p,m+1,t); //递归对左数组进行归并 MergeSort(p,s,m,t); //合并数组 } } int main() { int n;//n为输入数据的个数 int p[100]; cin>>n; for(int i=0; i<n; i++) //输入n个数据 cin>>p[i]; Merge(p,0,n-1); //调用函数进行归并 for(int i=0; i<n; i++) cout<<p[i]<<" "; //输出排列好的序列 cout<<endl; return 0;
}
Input
n和n个整数
Output
从小到大排序
Sample Input
10
2 1 3 5 4 6 7 9 8 10
Sample Output
1 2 3 4 5 6 7 8 9 10
#include <iostream>
using namespace std;
void MergeSort(int p[],int s,int m,int t)
{
int q[100]; //临时数组q[100]用来存放排好的序列
int i,j,k; //i作为左数组起始位置,j作为右数组起始位置,k为临时数组位置
for (i=s,j=m+1,k=0; k<=t-s; k++)
{
if (i==m+1) //当i到达左数组的最后时,将右数组余下元素复制到临时数组中
{
q[k]=p[j];
j++;
continue;
}
if (j==t+1) //当j达到右数组最后时,将左数组剩余元素复制到临时数组中
{
q[k]=p[i];
i++;
continue;
}
if(p[i]<p[j])
{
q[k]=p[i];
i++;
}
else
{
q[k]=p[j];
j++;
}
}
for(i=s,j=0; i<=t; i++,j++) //将临时数组的对应各项值赋给数组p[100]
p[i]=q[j];
}
void Merge(int p[],int s,int t)
{
if(s<t)
{
int m=(s+t)/2;
Merge(p,s,m); //递归对左数组进行归并
Merge(p,m+1,t); //递归对左数组进行归并
MergeSort(p,s,m,t); //合并数组
}
}
int main()
{
int n;//n为输入数据的个数
int p[100];
cin>>n;
for(int i=0; i<n; i++) //输入n个数据
cin>>p[i];
Merge(p,0,n-1); //调用函数进行归并
for(int i=0; i<n; i++)
cout<<p[i]<<" "; //输出排列好的序列
cout<<endl;
return 0;
}
归并排序原理：先将数据分开排序，然后再合并起来，最后形成一个排好的序列。 并归排序有一个关键步骤：合并两个排序好的序列。
方法是：两个序列中的数相互比较，将较小的数先插入新的序列中。
所谓归并是指将若干个已排好序的部分合并成一个有序的部分。
