Pythonは各種データ構造とアルゴリズムを実現---カウントソート

カウントソート
仮定前提:n個の入力要素のそれぞれは0〜k区間の整数であり、kは整数である
基本思想:入力要素xごとに、xより小さい要素の個数を決定する.この情報を利用すると,xを出力配列の位置に直接置くことができる.例えば、17個の要素がxより小さい場合、xは18番目の出力位置に置くべきである.いくつかの要素が同じである場合、このスキームは少し変更されます.

#coding:utf-8
a=[2,5,3,0,2,3,0,3]
def counting_Sort(A,B,K):
    #------------   -------------
    A_len=len(A)
    C=[0 for w in xrange(0,K+1)]    #xrange(0,k)，    K，
    B=[0 for w in xrange(0,A_len)]  # A   
    for i in xrange(0,K+1):         #    ,C 0  ，  max(a),    max(a)
        C[i]=0
    #----------  -------------    
    for j in xrange(0,A_len):
        C[A[j]]=C[A[j]]+1
    #-----------  -------------
    for i in xrange(1,K+1):
        C[i]=C[i]+C[i-1]
    #------------  -------------
    for j in xrange(A_len-1,-1,-1):#xrange(A_len-1,-1,-1)，j 7,6，。。。0，
        C[A[j]]=C[A[j]]-1
        B[C[A[j]]]=A[j]
    return B
M=[-1 for w in xrange(0,len(a))]#     
print 'before Counting_Sort:',a
print 'after Counting_Sort:',counting_Sort(a,M,max(a))