c - 数字的输入和输出如何在C中对数组进行排序？

Question

下面的代码如何打印排序的数组？我无法理解这背后的逻辑。

#include <stdio.h>

int a[1000000];

int main(void) {
    int t, i = 0, temp;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d", &temp);
        a[temp]++;
    }
    for (i = 0; i <= 1000000; i++) {
        while (a[i] != 0) {
            printf("%d\n", i);
            a[i]--;
        }
    }
    return 0;
}

Answer 1

首先，数组应该是a[1000001]，或者for循环应该是for(i=0;i<1000000;i++) .假设第二个答案

据我了解，数组中允​​许的最大数量必须为 999999。程序的主要逻辑(实现计数排序)是:

1. 计算范围 (0 - 999999) 内每个可能数字的频率。
2. 从 0 到 999999 遍历每个可能的数字并检查它的频率，打印它在原始数组中出现的次数

---

int a[1000000]; : 这声明了一个数组来保存从 0 到 999999 的每个数字的频率，每个数字的频率与数字本身具有相同的索引，即数字 n 的频率将在 a[n]。

---

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

此代码扫描每个元素并更新其频率(每次出现增加 1)。

---

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

这会遍历 0 - 999999 中的每个元素，并且对于每个元素: 打印元素并将其频率减 1 直到其频率变为 0，即打印元素与其频率相同的次数。

---

为什么会这样？

我们得到一个要按升序排序的数组(从代码中假设)。升序表示先小数。

因此，我们从范围内可能的最小数字开始，并检查它是否存在。如果它出现在数组中，我们打印它在数组中出现的次数。完成最小的数字后，我们继续下一个最小的数字并重复相同的操作。

重复相同的操作直到 999999 将确保打印的数组现在按升序排列，因为我们首先打印数字较小的数组，并且与原始数组的次数相同，因此，不会出现比原始数组更多或更少的数字.