算法笔记(六):计数排序和基数排序
(一)说明
这里我是按自己的理解去实现的,时间复杂度和空间复杂度和算法导论上的可能不一样,感兴趣的话参考下就行,感觉最重要的还是算法思想。根据算法性能去实现算法以后再研究。
(二)计数排序
计数排序的基本思想是:对每一个输人元素x,确定小于x 的元素个数。 利用这一信息,就 可以直接把x放到它在输出数组中的位置上了。 例如,如果有17个元素小于x,则x就应该在第18个输出位置上。 当有几个元素相同时,这一方案要略做修改。 因为不能把它们放在同一个输出位置上。
从这段话我们可以得出,我们要处理的事情其实就2个:
1、获取小于x的元素的个数k,然后将x放到k+1的位置上(当然,因为python列表的索引是从0开始的,所以代码就没必要+1了,直接放到索引k上就行了(就比如:有4个元素小于x,那么此时a[4] = x就行了,因为a[0] a[1] a[2] a[3]))
2、处理相同元素的情况。
实现代码:
1 #计数排序 2 def conutingsort(a): 3 b = [0 for i in range(len(a))] #初始化输出序列 4 #2个for循环获取小于x的元素的个数,5-9行 5 for i in range(len(a)): 6 k = 0 7 for j in range(len(a)): 8 if a[i] > a[j]: 9 k += 1 10 #这个if else,处理同名元素的情况,b.count(a[i])返回a[i]元素出现的个数 11 if a[i] in b: 12 b[k + b.count(a[i])] = a[i] 13 else: 14 b[k] = a[i] 15 return b 16 17 a = [5,2,4,7,1,3,2,6,-1,-6] 18 19 print(conutingsort(a))
(三)基数排序
感觉这种方式单独对正整数进行排序还好,如果考虑负数和小数的问题,问题有点复杂,甚至于可能要借用其他排序算法去处理。看算法导论上面的意思好像也是针对正整数的排序算法,感觉写这本书的大牛文笔好像不太好,没有深入浅出的感觉,或者是翻译的文笔不行。
基数排序,我个人的理解是,例如:对列表a = [720,328,278,356,789,234,123]进行排序
1、先按个位数进行排序 ,得到结果[720,123,234,356,328,278,789]
2、在第一步的基础上,按十位数进行排序,得到结果[720,123,234,328,356,278,789]
3、在第二步的基础上,按百位数进行排序,得到结果[123,234,278,328,356,720,789]
这样,有多少位数,就执行多少轮。最重要的是:每一轮结束时,一定要更新列表,然后下一轮排序是在这个的基础上进行的
实现代码:
**就是幂,例如x**y 就是 x的y次幂
% 返回除法的余数
[a for b in s for a in b] 这个是2重的列表生成式,不了解列表生成式的可以单独去了解下
1 #基数排序 2 def radixsort(a, d): # 最大位数是几,d就填几 3 for i in range(d): # d轮排序 4 s = [[] for k in range(10)] 5 for j in a: 6 s[int(j / (10 ** i)) % 10].append(j) 7 a = [a for b in s for a in b] #更新列表a 8 print(a) 9 return a 10 11 a = [720,328,278,356,789,234,123,113,113,999,789,9999,8999] 12 13 print(radixsort(a,4))
可以看到,前面4个就是每一轮排序后的结果
上一篇: JavaScript HTML 的 DOM 属性总结(代码实例)
下一篇: 前端之HTML