利用队列进行数字排序
对于 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 <math.h>
#include <stdio.h>
#include <stdlib.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;
}</pre>
这道题暂未补解析。