python计数排序和基数排序算法实例

一、计数排序

计数排序(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 randomdef 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中值

Posted in 未分类

发表评论