计数排序、桶排序python实现

深藏阁楼爱情的钟 2022-07-17 02:53 218阅读 0赞

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 在CODE上查看代码片 派生到我的代码片

  1. def countsort(lista):
  2. leng=len(lista);
  3. c=[];
  4. res=[];
  5. for i in range(0,100):
  6. c.append(0);
  7. for i in range(0,leng):
  8. c[lista[i]]=c[lista[i]]+1;
  9. res.append(0);
  10. for i in range(0,100):
  11. c[i]=c[i-1]+c[i]; #c中此时存放的是小于或者等于i的数字的个数
  12. for i in range(leng-1,-1,-1):
  13. res[c[lista[i]]-1]=lista[i];
  14. c[lista[i]]=c[lista[i]]-1;
  15. return res;
  16. lista=[5,4,2,5,1,7]; #计数排序测试代码
  17. lista=countsort(lista);
  18. print lista;

2.桶排序

桶排序介绍及C语言实现在：桶排序(链接)

[python] view plain copy 在CODE上查看代码片 派生到我的代码片

  1. class node:
  2. def __init__(self,k):
  3. self.key=k;
  4. self.next=None;
  6. def bucketsort(lista):
  7. h=[];
  8. for i in range(0,10):
  9. h.append(node(0));
  10. for i in range(0,len(lista)):
  11. tmp=node(lista[i]);
  12. map=lista[i]/10;
  13. p=h[map];
  14. if p.key is 0:
  15. h[map].next=tmp;
  16. h[map].key=h[map].key+1;
  17. else:
  18. while(p.next !=None and p.next.key<=tmp.key):
  19. p=p.next;
  20. tmp.next=p.next;
  21. p.next=tmp;
  22. h[map].key=h[map].key+1;
  23. k=0;
  24. for i in range(0,10):
  25. q=h[i].next;
  26. while(q != None ):
  27. lista[k]=q.key;
  28. k=k+1;
  29. q=q.next;
  30. return lista;
  31. lista=[1,4,23,45,97,22,10,4]; #桶排序测试代码
  32. bucketsort(lista);
  33. print lista;

发表评论

表情：
评论列表 （有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

    相关 python 实现桶排序

    前言 桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使

    水深无声水深无声/ 0 赞/ 406 阅读