说明

对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了

代码

from typing import List,Optional
import math
def counting_sort(A:List[int],k:int)->List[int]:
    C = [0]*(k+1)
    B = [0]*len(A)
    for j in range(len(A)):
        C[A[j]] += 1
    for i in range(1,k+1):
        C[i] = C[i]+C[i-1]
    for j in range(len(A)-1,-1,-1):
        B[C[A[j]]-1] = A[j]
        C[A[j]]-=1
    return B

A = [2,5,3,0,2,3,0,3]
B = counting_sort(A,5)
print(B)