简答题 偏难
#7301

利用队列进行数字排序 对于 N 个数字, 有人提出了如下的排序策略: 例如, 对于数字 53、 47、 85、 38、 64、 23 先建立 10 个队列(0…

利用队列进行数字排序

对于 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处理)

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

时间限制: 1000

内存限制: 65535

输入

分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999

输出

输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行: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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;math.h&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define ElemType int #define MaxSize 2000 typedef struct ss {   ElemType data[MaxSize];   int front, rear; } SqQueue; void InitQueue(SqQueue *&amp;q) {   q = (SqQueue *)malloc(sizeof(SqQueue));   q-&gt;front = q-&gt;rear = -1; } void DestoryQueue(SqQueue *&amp;q) { free(q); } bool QueueEmpty(SqQueue *q) { return (q-&gt;front == q-&gt;rear); } bool enQueue(SqQueue *&amp;q, ElemType e) {   if (q-&gt;rear == MaxSize - 1)     return false;   q-&gt;rear++;   q-&gt;data[q-&gt;rear] = e;   return true; } bool deQueue(SqQueue *&amp;q, ElemType &amp;e) {   if (q-&gt;rear == q-&gt;front)     return false;   q-&gt;front++;   e = q-&gt;data[q-&gt;front];   return true; } int Num(int h) // 返回h的位数 {   int i = 0;   if (h == 0)     return 1;   while (h &gt; 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 &gt; k)     return 0;   else if (num &lt;= 9 &amp;&amp; g == 1)     return num;   while (num &gt;= 10 &amp;&amp; i &lt; 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", &amp;n);   SqQueue *q[10];   for (i = 0; i &lt; 10; i++) {     InitQueue(q[i]);   }   for (i = 0; i &lt; n; i++) {     if (i != n - 1)       scanf("%d ", &amp;a[i]);     else       scanf("%d", &amp;a[i]);   }                       // a[i]='\0';   for (i = 0; i &lt; n; i++) // 找出最大值   {     k = Num(a[i]);     if (k &gt; max)       max = k;   }   //  printf("%d\n",max);   for (i = 1; i &lt;= max; i++) //   {     printf("Step%d.\n", i);     for (j = 0; j &lt; 10; j++) { // 建立0-9的队对应的数字并输出       for (k = 0; k &lt; n; k++) {         if (data(i, a[k]) == j)           enQueue(q[j], a[k]);       }     }     t = 0;     for (j = 0; j &lt; 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 &lt; n; i++) {     printf("%d ", a[i]);   }   printf("\n");   system("pause");   return 0; }</pre>
这道题暂未补解析。