c - TSORT 数组功能

Question

最近我在 spoj 上解决一个关于排序的问题，我使用 python 解决了它，但它给了我 tle，然后我遇到了同样问题的代码，该代码工作正常，但任何人都可以向我解释它的工作原理，特别是ar[a]++ 和 ar[i]-- 部分

#include <stdio.h>

int ar[1000001];

int main(){
    int i,j,a;
    scanf("%d",&j);

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

    for (i=0;i<1000001;i++){
        while(ar[i]>0){
            printf("\n%d",i);
            ar[i]--;
        }
    }

    return 0;
}

Answer 1

它被称为 counting sort (维基链接)。该代码示例假设值限制在 0 -> 1000000 范围内。 ar[a]++ 递增数组中的值，而 ar[i]-- 递减数组中的值。