0

以下是用于按非递减顺序对数字进行排序的代码：

#include<stdio.h>
#include<stdlib.h>
# define size 1000001
static int a[size];
int main()
{
  int t, k, i;
  scanf("%d", &t);
  for(i = 0; i < t; i++)
  {
    scanf("%d", &k);
    a[k] += 1;
  }
  for(i = 0; i < 1000001; i++)
  {
    while(a[i]-- != 0)
      printf("%d\n", i);
  }
  return 0;
}

如果有人可以向我解释代码，那将是非常有帮助的。我已经浏览了代码，但我不知道它如何对数字进行排序。在任何地方都没有进行交换，但它仍然可以在 c++ 编辑器中工作。

4

6 回答 6

2

这个程序不会在数学意义上对数字进行排序，但这并不重要，因为它会给你一种这样做的错觉。

程序要求t，最好命名为numberOfValues... 您将输入的值的数量。

数组a[size]可以被认为是size值的桶。在您的程序中，这些buckets只是计数器。每个桶都有一个数字，从 0 到大小。输入值时5，桶a[5]的计数增加。这一直持续到所有桶都设置完毕。

然后程序通过存储桶运行。您的大多数存储桶都是空的，但是当存储桶不为零时（while a[i] != 0--暂时忽略丢失--的内容），存储桶需要“清空”，同时需要考虑其内容。桶a[i]保存i元素的计数，因此循环打印出i排序中的下一个值，同时减少计数 ( a[i]--)。这种情况一直持续到桶为空（== 0）并且程序移动到下一个桶。

最终，您的所有存储桶都已清空，排序完成。

于 2013-07-02T11:15:57.290 回答
0

考虑 i=0; 然后a[i]--!=0将被执行，直到 value ata[i]不变为zero。当 value ata[i]变为zerowhile 循环将被终止并且循环的下一次迭代for将开始。

于 2013-07-02T11:15:03.210 回答
0

代码对数组中的每个值进行迭代a。数组中的每个值a[i]都在 while 循环中进行迭代。while(a[i]--!=0)检查 a[i] 的值是否为零。如果不是，则执行循环体。当控件进入循环体时，将 a[i] 值递减。例如）如果 a[i]=6，输出将是：

5
4
3
2
1
0
于 2013-07-02T11:13:28.667 回答
0

a[i]每次打印时递减变量直到它为0

于 2013-07-02T11:05:31.847 回答
0

没有交换，因为不需要：数字不会像往常一样存储，它使用一个巨大的数组来标记已输入的数字：

如果添加数字 200，它存储 array[200]=1。如果再加 200，则 array[200]=2。

然后，它以下列方式打印数组：假设您有 [0,1,2,1,0,0...]，所以有一个 1、两个 2、一个 3... 所以它只显示 1 ,2,2,3

于 2013-07-02T11:12:11.323 回答
0

这是一个不错的代码，但它的空间复杂度很高。

这部分代码

for(i = 0; i < t; i++)
  {
    scanf("%d", &k);
    a[k] += 1;
  }

存储输入数字的频率（有点像散列）

说如果我进入 5 4 2 4 2

然后

a[5] =1 
a[4] =2
a[2] =2

所有其他人将为零

所以如果你想说在数组中找到“n”的频率，那么只需打印a[n]

现在让我们来回答你的问题

此代码如何对数字进行排序？

有什么用while(a[i]--!=0)？

回答第一个问题：

我们依次从 0 到 1000001，所以如果输入 4 2 5 6

当循环从 0 到 100001 时，它首先检查 a[2] !=0 然后 a[4] 然后 a[5] 然后 a[6] 打印所有非零频率项。

所以根据检查首先打印 2 4 5 6

回答第二个问题：

为什么不是while(a[i]!=0)因为我只检查它是否非零，如果它的非零让打印数字

但是说我输入了 4 3 2 4 2

那么输出应该打印 2 2 3 4 4

所以while(a[i] --!=0)使用它打印数字 a[i] 次说如果

a[4]=2 这意味着 4 存在 2 次，因此它应该打印 4 4 所以 while 循环运行两次 a[4] =2

于 2021-06-14T15:56:24.633 回答