计数排序、桶排序python实现
http://blog.csdn.net/u011608357/article/details/37725455
计数排序在输入n个0到k之间的整数时,时间复杂度最好情况下为O(n+k),最坏情况下为O(n+k),平均情况为O(n+k),空间复杂度为O(n+k),计数排序是稳定的排序。
桶排序在输入N个数据有M个桶时,如果每个桶的数据接近N/M个且桶内使用基于比较的排序,则桶排序的时间复杂度为O(N+M*N/M*log(N/M)).如果N=M时,每个桶只有一个数据,时间复杂度降低为O(N).
桶排序的时间复杂度为O(N+M),桶排序是稳定的排序
1.计数排序
计数排序介绍及C语言实现在:计数排序(链接)
[python] view plain copy
- def countsort(lista):
- leng=len(lista);
- c=[];
- res=[];
- for i in range(0,100):
- c.append(0);
- for i in range(0,leng):
- c[lista[i]]=c[lista[i]]+1;
- res.append(0);
- for i in range(0,100):
- c[i]=c[i-1]+c[i]; #c中此时存放的是小于或者等于i的数字的个数
- for i in range(leng-1,-1,-1):
- res[c[lista[i]]-1]=lista[i];
- c[lista[i]]=c[lista[i]]-1;
- return res;
- lista=[5,4,2,5,1,7]; #计数排序测试代码
- lista=countsort(lista);
- print lista;
2.桶排序
桶排序介绍及C语言实现在:桶排序(链接)
[python] view plain copy
- class node:
- def __init__(self,k):
- self.key=k;
- self.next=None;
- def bucketsort(lista):
- h=[];
- for i in range(0,10):
- h.append(node(0));
- for i in range(0,len(lista)):
- tmp=node(lista[i]);
- map=lista[i]/10;
- p=h[map];
- if p.key is 0:
- h[map].next=tmp;
- h[map].key=h[map].key+1;
- else:
- while(p.next !=None and p.next.key<=tmp.key):
- p=p.next;
- tmp.next=p.next;
- p.next=tmp;
- h[map].key=h[map].key+1;
- k=0;
- for i in range(0,10):
- q=h[i].next;
- while(q != None ):
- lista[k]=q.key;
- k=k+1;
- q=q.next;
- return lista;
- lista=[1,4,23,45,97,22,10,4]; #桶排序测试代码
- bucketsort(lista);
- print lista;
还没有评论,来说两句吧...