题目

思路

显然是桶排序:将B出现在A中的元素放在一个桶里,没出现在A中的元素放在另一个桶里,两个桶分别排序后再输出.

代码

法一:

#include<stdio.h>
#include<stdlib.h>

typedef struct{int number;int pos;}Data;

int cmp1(const void *a,const void *b)  //按出现在A中的相对位置排
{
    Data *m=(Data*)a;
    Data *n=(Data*)b;
    return m->pos-n->pos;
}

int cmp2(const void *a,const void *b)  //升序
{
    int *m=(int*)a;
    int *n=(int*)b;
    return *m-*n;
}

int main()
{
    int m;
    scanf("%d",&m);
    int A[m];
    for(int i=0;i<m;i++)
    {
        scanf("%d",&A[i]);
    }
    int n;
    scanf("%d",&n); 
    int B[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&B[i]);
    }
    Data temp1[n];  //存出现在A中的元素对应的值和位置
    int temp2[n];  //存未出现在A中的元素
    int j=0,k=0;
    for(int i=0;i<n;i++)
    {
        int r;
        for(r=0;r<m;r++)
        {
            if(B[i]==A[r])   //出现在A中
            {
                temp1[j].number=B[i];  
                temp1[j].pos=r;   
                j++;
                break;
            }
        }
        if(r==m)   //没在A中
        {
            temp2[k]=B[i];
            k++;
        }
    }   
    qsort(temp1,j,sizeof(Data),cmp1);
    qsort(temp2,k,sizeof(int),cmp2);    
    for(int i=0;i<j;i++)
    {
        printf("%d ",temp1[i].number);
    }   
    for(int i=0;i<k;i++)
    {
        printf("%d ",temp2[i]);
    }
}