python计数排序与基数排序算法示例

#-*- coding:utf8 -*-
import random

def jishu(data, max):
    """
    基数排序:当输入的元素是 n 个 0 到 k 之间的整数时(k不能太大,即max不能太大)
    @param data: 需要排序的数组
    @param max: 最大的数
    """
    result = [None for i in xrange(len(data))]  # 最后的结果
    c = [0 for i in range(max+1)]
    # 用数组c统计每个值=d的元素个数
    for d in data:
        c[d] = c[d] + 1
    # c[i]表示data中值<=i 的元素个数
    for i in range(1, max+1):
        c[i] = c[i] + c[i-1]
    # 在将C中的元素倒着打印出来就是排序好的
    for j in xrange(len(data)-1, -1, -1):
        result[c[data[j]]-1] = data[j]
        c[data[j]] = c[data[j]] – 1
    return result
 
if __name__ == '__main__':
    #制造1000个0到100的数字
    print jishu([random.randint(0, 100) for i in range(1000)], 100)

#-*- coding:utf8 -*-
import random
def jichu(data, length):
    """
    基数排 lsd
    @param data: 需要排列的组合
    @param length: 最大的数据是几位
    """
    for l in xrange(length):
        s = [[] for i in xrange(10)] 
        for d in data:
            s[d/(10**l) % 10].append(d)
        data = [d for s_list in s for d in s_list]
    return data
 
if __name__ == '__main__':
    list = [random.randint(1, 99999999) for i in xrange(99)]  # 制造99个数据
    print jichu(list, 8)