基于python进行桶排序与基数排序的总结
本文首先举例阐述了两种排序方法的操作步骤，然后列出了用python进行的实现过程，最后对桶式排序方法的优劣进行了简单总结。
一、桶排序：
排序一个数组[5,3,6,1,2,7,5,10]
值都在1-10之间，建立10个桶：
[0000000000]桶
[12345678910]桶代表的值
遍历数组，第一个数字5，第五个桶加1
[0000100000]
第二个数字3，第三个桶加1
[0010100000]
遍历后
[1110211001]
输出
[123556710]
代码：
defbucket_sort(lst): buckets=[0]*((max(lst)-min(lst))+1) foriinrange(len(lst)): buckets[lst[i]-min(lst)]+=1 res=[] foriinrange(len(buckets)): ifbuckets[i]!=0: res+=[i+min(lst)]*buckets[i] returnres
二、基数排序：
例如，对如下数据序列进行排序。
192,221,12,23
可以观察到它的每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。基数排序方法对任一子关键字排序时必须借助于另一种排序方法，而且这种排序方法必须是稳定的。对于多关键字拆分出来的子关键字，它们一定位于0-9这个可枚举的范围内，这个范围不大，因此用桶式排序效率非常好。
代码：
fromrandomimportrandint defradix_sort(lis,d): foriinxrange(d):#d轮排序 s=[[]forkinxrange(10)]#因为每一位数字都是0~9，故建立10个桶 forjinlis: s[j/(10**i)%10].append(i) li=[aforbinsforainb] returnli
对数组中的元素按照从低位到高位排序，对于[192,221,12,23]第一轮按照个位数字相同的放在一组，是s[1]=[221],s[2]=[192,12],s[3]=23,第二轮按照十位数字进行排序，s[1]=[12],s[2]=[221,23],s[9]=[192],第三轮按照百位数字进行排序，s[0]=[12,23],s[1]=[192],s[2]=[221]
总结：
桶排序与基数排序常作为桶式排序出现，基数排序进行了多轮的桶排序。桶式排序不再是一种基于比较的排序方法，它是一种比较巧妙的排序方式，但这种排序方式需要待排序的序列满足以下两个特征：待排序列所有的值处于一个可枚举的范围之类；待排序列所在的这个可枚举的范围不应该太大，否则排序开销太大。可以用于学生成绩的排序，因为在若干学生中成绩的范围仅在100以内。
桶式排序的空间开销较大，它需要两个数组，第1个buckets数组用于记录“落入”各桶中元素的个数，进而保存各元素在有序序列中的位置，第2个数组用于缓存待排数据。它只能排整形数组。而且当k较大，而数组长度n较小，即k>>n时，辅助数组C[k+1]的空间消耗较大。
以上这篇基于python进行桶排序与基数排序的总结就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。