利用队列进行数字排序

OpenJudge利用队列进行数字排序

题目：
描述
对于N个数字，有人提出了如下的排序策略：

例如，对于数字53、47、85、38、64、23

先建立10个队列(0到9），用于存放数字的大小，将这N个数字依个位存放入各自的队列之中，然后再按队列0到队列9依次出队。

例如，对于上面的数字，依次进队后，结果如下：

队列3：53、23　队列4：64　队列5：85　队列7：47　队列8：38

将其依次出队后，结果为53,23,64,85,47,38

然后，再将方才出队后的队对，依照十位放入各自的队列之中，然后再按队列0到队列9依次出队

例如，对于上面刚刚出队的序列53,23,64,85,47,38，将其依次进队，结果如下：

队列2：23　队列3：38　队列4：47　队列5：53　队列6：64　队列8：85

将其依次出队后，结果为23,38,47,53,64,85.因为这组数字最大只是两位数，所以排序结束。

如果还有更大的数字，那么，接下来就是其百位、千位……（如果位数不够，就补0.比如最大的数字是四位数，那么数字23就当成0023处理）

请根据上述算法，对这些数字进行排序

输入
分为两行，第一行为一个数字N(1 <= N <= 100)，表示数字的个数
第二行为N个数字（都是非负数），以空格相隔，最大的数字不超过32位整数的表示范围。
输出
输出两个部分
第一个部分为第一次进队出队的结果，先显示一行：Step1.
之后用Queue0:…表示，共10行，结果用空格分隔，下同
之后为第二次进队出队的结果（如果需要第二次进队出队的话），先显示一行：Step2.
之后仍然用Queue0:…表示，共10行
之后如果需要的话，则分别显示第三次、第四次的进队出队结果
第二部分为一行，即将数字排序后的结果（升序排序）

样例输入

20
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

样例输出

Step1.
Queue0:0
Queue1:41 81 61 91
Queue2:62 42
Queue3:
Queue4:34 24 64
Queue5:5 45 95
Queue6:36
Queue7:67 27 27
Queue8:78 58
Queue9:69
Step2.
Queue0:0 5
Queue1:
Queue2:24 27 27
Queue3:34 36
Queue4:41 42 45
Queue5:58
Queue6:61 62 64 67 69
Queue7:78
Queue8:81
Queue9:91 95
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95

思路：如题目要求，建立队列存储即可实现。

代码：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define ElemType int
#define MaxSize  2000
typedef struct ss{
    ElemType data[MaxSize];
    int front,rear;   
}SqQueue;

void InitQueue(SqQueue* &q)
{ 
    q=(SqQueue*)malloc(sizeof(SqQueue));
    q->front=q->rear=-1;
}

void DestoryQueue(SqQueue* &q)
{
    free(q);
}

bool QueueEmpty(SqQueue* q)
{
    return (q->front==q->rear);
}

bool enQueue(SqQueue*& q,ElemType e)
{
    if(q->rear==MaxSize-1)
        return false;

    q->rear++;
    q->data[q->rear]=e;
    return true;

}

bool deQueue(SqQueue*& q,ElemType &e)
{
    if(q->rear==q->front)
        return false;
    q->front++;
    e=q->data[q->front];
    return true;    
}

int Num(int h)       //返回h的位数
{
    int i=0;
    if(h==0) return 1;
    while(h>0){
        i++;
        h/=10;
    }
    return i;
}

int data(int g,int num) //返回num的第g位数字
{
    int result,i=1;
    int k=Num(num);  //获取位数
    if(num==0||g>k) return 0;
    else if(num<=9&&g==1) return num;
 
    
    while(num>=10&&i<g){
        num/=10;
        i++;
    }
    result=num%10;
     return result;
}

 int main ()
 {
      int n,i=0,j,a[100],max=0,k=0,e,t=0;
      scanf("%d\n",&n);

      SqQueue *q[10];

      for(i=0;i<10;i++){
          InitQueue(q[i]);
      }
      
   for(i = 0; i < n; i++){
          if(i!=n-1) scanf("%d ",&a[i]);
          else scanf("%d",&a[i]);
      }   // a[i]='\0';

    for(i = 0; i < n; i++)  //找出最大值
    {
        k=Num(a[i]);
        if(k>max)
            max=k;      
    }

  //  printf("%d\n",max);
      for(i = 1; i <= max; i++)     //
    {
        printf("Step%d.\n",i);
        
        for(j=0;j<10;j++) {         //建立0-9的队对应的数字并输出

            for(k=0;k<n;k++)
            {
                if(data(i,a[k])==j)
                    enQueue(q[j],a[k]);
            }
            

        } 
           t=0;
           for(j=0;j<10;j++){
              printf("Queue%d:",j);
              while(!QueueEmpty(q[j])){
                deQueue(q[j],e);
               a[t++]=e;
               printf("%d ",e); 
            }printf("\n");
      }
        //printf("\n");
    }

   for(i=0;i<n;i++){
       printf("%d ",a[i]);
   }printf("\n");


   system("pause");
   return 0;

 }

记得点赞