정렬 알고리즘: 계수정렬

계수정렬..

조건만 잘 맞으면 퀵정렬보다 빠른.. 그런 정렬.. 시간복잡도가 O(N+K)라고한다. N은 숫자개수 K는 최대숫자

 

근데 이게..

숫자들이 일단 정수여야함

그리고 배열을 하나 더 만들기 때문에 공간복잡도가 높음.

 

어떻게하냐면..

배열을 쭉 돌면서 어떤 숫자가 몇번 나왔는지를 다 카운트함

그러고나서 그냥 0부터 시작해서~최대값까지 각 숫자를 카운트만큼 출력해주면됨

 

array = [7,5,9,0,3,1,6,2,9,1,4,8,0,6,2]

count=[0]*(max(array)+1)
for i in range(len(array)):
    count[array[i]]+=1 #각 숫자가 나오는 횟수를 셈..

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end='')