计数排序算法，仅针对整数，且能确定元素的范围，平均时间复杂度O（n）：

python 实现：

import random 

A_range = 10000
A=[x for x in range(10000)]
random.shuffle(A)

#only for integer and must in range 0~k
def counting_sort(A,k):
    B=[0 for x in range(len(A))]
    C=[0 for x in range(k)]
    for i in range(len(A)):
        C[A[i]] = C[A[i]]+1

    for j in range(k):
        C[j] = C[j] +C[j-1]

    for l in range((len(A)-1),-1,-1):
        B[C[A[l]]-1] = A[l]
        C[A[l]] = C[A[l]] -1
    return B


B=counting_sort(A,A_range+1)
print B