C++习题-归并排序

C++习题-归并排序

时间: 1ms        内存:128M

描述:

有数列{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;

}

输入:

n和n个整数

输出:

从小到大排序

示例输入:

10
2 1 3 5 4 6 7 9 8 10

示例输出:

1 2 3 4 5 6 7 8 9 10 

提示:

参考答案(内存最优[1084]):

#include <stdio.h>
int main()
{
    int i=0,d;
    int a[10],b,c;
    scanf("%d",&c);
    for(i=0;i<c;i++)scanf("%d",&a[i]);
        for(i=0;i<c-1;i++)
        for(d=0;d<c-i-1;d++)
        if(a[d]>a[d+1])
        {
            b=a[d+1];
            a[d+1]=a[d];
            a[d]=b;
            }
    for(i=0;i<c;i++)printf("%d ",a[i]);
    return 0;
}

参考答案(时间最优[0]):


#include<iostream>
using namespace std;
void MergeSort(int p[],int s,int m,int t)
{
     int q[100];                        //q[100]用来存放排好的序列
	 int i=s;
	 int j=m+1;
	 int k=s;
while(i<=m&&j<=t)
	 {
		 if(p[i]<=p[j])
			 q[k++]=p[i++];
		 else
			 q[k++]=p[j++];
	 }
	 if(i<=m)
		 while(i<=m)
			 q[k++]=p[i++];
		 else while(j<=t)
			 q[k++]=p[j++];
		 for(int n=s;n<=t;n++)
             p[n]=q[n];
}
 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;
	 int p[100];
	 cin>>n;
	  for(int i=0; i<n; i++)
         cin>>p[i];
	 Merge(p,0,n-1);
	 for(int j=0;j<n;j++)
		 cout<<p[j]<<" ";
	 cout<<endl;
	 return 0;
 }

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注