基数排序，平均时间复杂度O(n):

       基数排序依赖于稳定排序，对每个字段按优先级从低到高进行稳定排序，规模为n的数据，d个字段，每个字段可能取值为0~k则时间耗费为Θ（d(n+k）)

       基于计数排序的十进制整数基数排序，可以看出计数排序是稳定的，python实现：

import random 
import math

A_range = 100
A = []
for i in range(A_range):
    A.append(random.randint(0,A_range) )

#must make sure the count of columns (named d)

k = 10  #for decimal base
def radix_sort(A,d):
    
    A_sub=[0 for x in range(len(A))]
    for i in range(d):
        for j in range(len(A)):
            A_sub[j] = A[j]/(k**i) % k
        A= counting_sort(A,A_sub,k)
    return A

def counting_sort(A,A_sub,k):
    B=[0 for x in range(len(A))]
    C=[0 for x in range(k)]

    for i in range(len(A)):
        C[A_sub[i]] = C[A_sub[i]]+1

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

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

    return B

A = radix_sort(A,int(math.log(A_range,k))+1)
print A