计数排序、桶排序python实现

深藏阁楼爱情的钟 2022-07-17 02:53 175阅读 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语言实现在：[计数排序(链接)][Link 1]

**\[python\]** [ view plain][view plain] [ copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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语言实现在：[桶排序(链接)][Link 2]

**\[python\]** [ view plain][view plain] [ copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  class node:
2.  def \_\_init\_\_(self,k):
3.  self.key=k;
4.  self.next=None;
5.  
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;

[Link 1]: http://blog.csdn.net/u011608357/article/details/21328735
[view plain]: http://blog.csdn.net/u011608357/article/details/37725455#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/425175
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/425175/fork
[Link 2]: http://blog.csdn.net/u011608357/article/details/21344315