Python实现各类数据结构和算法---计数排序

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))