一、计数排序
计数排序(Counting sort)是一种稳定的排序算法
算法的步骤如下：
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K)，空间复杂度为O(N+K)。当K不是很大时，这是一个很有效的线性排序算法。
以下是测试代码：
代码如下:
#-*- 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
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中值