Manchester


私信TA

用户名:wenyajie

访问量:156617

签 名:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

等  级
排  名 1
经  验 37400
参赛次数 1
文章发表 188
年  龄 0
在职情况 学生
学  校 Qing Dao University
专  业 计算机科学

  自我简介:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

解题思路:
1.采用分治法思想,把整个序列,拆分为多个子序列,分别对多个子序列排序,再把排好序的子序列合并起来,具体如图:

2018-01-04 19-54-31屏幕截图.png

拆分过程实现:

void Mesort(int *A,int *B,int left,int right)//B[],用于合并排序时
{
 if(left<right)   //子序列长度大于一,则继续分
 {
    int i=(left+right)/2;   //求中点  
      Mesort(A,B,left,i);    //左半部分拆分
      Mesort(A,B,i+1 ,right);  //右半部分拆分
 }
}


合并加排序实现:

void Merge(int *A,int *B,int left,int middle,int right)
{
int  i=left,j=middle+1,k=left;  //i为右半部分第一个数的下标,j为左半部分第一个数的下标
                                //B[]用于存放排好序的序列
while((i<=middle)&&(j<=right))  //左右两部分同时遍历
{
    if(fabs(A[i])>=fabs(A[j]))  //把左右两部分的绝对值大的存入B[]
      B[k++]=A[i++];
     else
      B[k++]=A[j++];
}
//这里把剩余部分存到B[]里,因为每一个子序列都是排好序的,直接存放就可
if(i>middle)    
    for(int q=j;q<=right;q++)  //左半部分序列有剩余
       B[k++]=A[q];
else
    for(int q=i;q<=middle;q++) //右半部分序列有剩余
       B[k++]=A[q];

}


把排好序的部分B[],复制回A[].

void copy(int *A,int *B,int left,int right)
{
   for(;left<=right;left++)
       A[left]=B[left];
}

完整递归:

void Mesort(int *A,int *B,int left,int right)
{
 if(left<right)
 {
    int i=(left+right)/2;
      Mesort(A,B,left,i);
      Mesort(A,B,i+1 ,right);
      Merge(A,B,left,i,right);
    copy(A,B,left,right);
 }
}

注意:只以0结束的话,提交会输出超限,得加上以文件末尾结束

参考代码:

#include <stdio.h>
#include <malloc.h>
#include <math.h>
void input( int *A, int n );
void output( int *A, int n );
void Mesort( int *A, int *B, int left, int right );
void Merge( int *A, int *B, int left, int middle, int right );
void copy( int *A, int *B, int left, int right );

/*--------------------------------------------------------*/
int main()
{
    int    *A, *B;
    int    n;
    while ( scanf( "%d", &n ) != EOF && n != 0 )
    {
        A    = (int *) malloc( n * sizeof(int) );
        B    = (int *) malloc( n * sizeof(int) );
        input( A, n );
        Mesort( A, B, 0, n - 1 );
        output( A, n );
        free( A );
        free( B );
    }
    return(0);
}


/*--------------------------------------------------------*/
void Mesort( int *A, int *B, int left, int right )
{
    if ( left < right )
    {
        int i = (left + right) / 2;
        Mesort( A, B, left, i );
        Mesort( A, B, i + 1, right );
        Merge( A, B, left, i, right );
        copy( A, B, left, right );
    }
}


/*--------------------------------------------------------*/
void Merge( int *A, int *B, int left, int middle, int right )
{
    int i = left, j = middle + 1, k = left;

    while ( (i <= middle) && (j <= right) )
    {
        if ( fabs( A[i] ) >= fabs( A[j] ) )
            B[k++] = A[i++];
        else
            B[k++] = A[j++];
    }

    if ( i > middle )
        for ( int q = j; q <= right; q++ )
            B[k++] = A[q];
    else
        for ( int q = i; q <= middle; q++ )
            B[k++] = A[q];
}

/*--------------------------------------------------------*/
void copy( int *A, int *B, int left, int right )
{
    for (; left <= right; left++ )
        A[left] = B[left];
}

/*-------------------------*/
void input( int *A, int n )
{
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &A[i] );
}

/*-------------------------*/
void output( int *A, int n )
{
    for ( int i = 0; i < n - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d\n", A[n - 1] );
}

别忘点赞哦-.-

附带一个选择排序实现:详解见1129题(在选择排序基础上加上个绝对值)

#include <stdio.h>
#include <malloc.h>
#include <math.h>
void sort( int n );
void input( int *A, int n );
void output( int *A, int n );
/*----------------------------------------------------*/
int main()
{
    int n;
    while ( scanf( "%d", &n ) != EOF && n != 0 )
        sort( n );
    return(0);
}

/*----------------------------------------------------*/
void sort( int n )
{
    int    *A;
    int    maxi, term;
    A = (int *) malloc( n * sizeof(int) );

    input( A, n );

    for ( int i = 0; i < n; i++ )
    {
        maxi = i;
        for ( int j = i; j < n; j++ )
        {
            if ( fabs( A[maxi] ) < fabs( A[j] ) )
                maxi = j;
        }

        if ( i != maxi )
        {
            term    = A[i];
            A[i]    = A[maxi];
            A[maxi] = term;
        }
    }

    output( A, n );
    return;
}
/*----------------------------------------------------*/
void input( int *A, int n )
{
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &A[i] );
}
/*----------------------------------------------------*/
void output( int *A, int n )
{
    for ( int i = 0; i < n - 1; i++ )
        printf( "%d ", A[i] );
    printf( "%d\n", A[n - 1] );
}

别忘点赞哦-.-


 

0.0分

4 人评分

  评论区

题目不是说所有值的绝对值不同吗?如果我输入是有些值相同,不是错误吗?
2020-02-19 10:46:43 | |
#include<stdio.h>
int main()
{
	int s[100],i,n,j,t;
	while(1)
	{
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++)
		scanf("%d",&s[i]);
		for(i=0;i<n-1;i++)
		{
			for(j=0;j<n-1-i;j++)
			{
				if(abs(s[j])>abs(s[j+1]))
				{
					t=s[j];
					s[j]=s[j+1];
					s[j+1]=t;
				}
			}
		}	
		for(i=n-1;i>=0;i--)
			printf("%d ",s[i]);
			printf("\n");
	}
	return 0;
 } 
哪位大佬帮我看看,超出界限50%,哪错了?
2019-04-05 15:46:37 | |
#include<stdio.h>
void sort(int a[],int n){
	int i,k,q;
	for(i=0;i<n;i++){
		for(k=0;k<n-i-1;k++){
			if((a[k]*a[k]) < (a[k+1]*a[k+1])){
				q=a[k];
				a[k]=a[k+1];
				a[k+1]=q;
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d ",a[i]);
	}
}
int main(){
	int n;
	int a[101];
	while(scanf("%d",&n)!=EOF){
		int i;
		for(i=0;i<n;i++){
			int t;
			scanf("%d",&t);
			a[i]=t;
		}
		sort(a,n);
		printf("\n");	
	}
	return 0;
}
感觉代码量好多
2019-03-13 16:54:58 | |
  • «
  • 1
  • »