# Sort II - Counting Sort

Ԑ : 1 sec, : 131072 KB
pł͂

# v\[g

v\[g͊evf 0 ȏ $k$ ȉłvf $n$ ̐ɑ΂Đ`($O(n + k)$)œȃ\[eBOASYłB

͐ $A$ ̊evf $A_j$ ɂāA$A_j$ ȉ̗vf̐JE^z $C$ ɋL^A̒lɏo͔z $B$ ɂ $A_j$ ̈ʒu߂܂B̗vfꍇlāAvf $A_j$ ói$B$ ɓjɃJE^ $C[A_j]$ ͏CKv܂Bڂ͈ȉ̋^R[hQlɂĂB

1 CountingSort(A, B, k)
2     for i = 0 to k
3         C[i] = 0
4
5     /* C[i]  i ̏oL^ */
6     for j = 1 to n
7         C[A[j]]++
8
9     /* C[i]  i ȉ̐̏oL^*/
10    for i = 1 to k
11        C[i] = C[i] + C[i-1]
12
13    for j = n downto 1
14        B[C[A[j]]] = A[j]
15        C[A[j]]--

$A$ ǂݍ݁Av\[g̃ASYŏɕёւo͂vO쐬ĂBL^R[hɏ]ăASYĂB

͂̍ŏ̍sɁA $A$ ̒\ $n$ ^܂BQsڂɁA$n$ ̐󔒋؂ŗ^܂B

## o

񂳂ꂽ1sɏo͂ĂB̘Avf͂P̋󔒂ŋ؂ďo͂ĂB

• $1 \leq n \leq 2,000,000$
• $0 \leq A[i] \leq 10,000$

7
2 5 1 3 2 3 0

0 1 2 2 3 3 5