기수 정렬

값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교함

시간복잡도 O(kN) / K는 데이터의 자릿수

계수 정렬

데이터의 최댓값 크기의 배열에 각 요소의 배열 등장 횟수를 count해 저장한 후 작은 인덱스값 순서대로 출력

O(n + k) (k는 Input 요소의 최댓값)( k가 작은 수라면 O(n),  k가 무한으로 커질 때는 O(무한)

import sys
N = int(sys.stdin.readline())
Nlist = [0] * 10001
for i in range(N):
    a = sys.stdin.readline()
    Nlist[int(a)] += 1

for j in range(1, 10001):
    if Nlist[j] >= 1:
        for k in range(Nlist[j]):
            print(j)