快速排序，归并排序，堆排序python实现

淡淡的烟草味﹌ 2022-07-17 02:53 280阅读 0赞

http://blog.csdn.net/u011608357/article/details/37724329

快速排序的时间复杂度最好情况下为O(n\*logn),最坏情况下为O(n^2),平均情况下为O(n\*logn),是不稳定的排序

归并排序的时间复杂度最好情况下为O(n\*logn),最坏情况下为O(n\*logn),平均情况下为O(n\*logn),是稳定的排序

堆排序的时间复杂度最好情况下为O(n\*logn),最坏情况下为O(n\*logn),平均情况下为O(n\*logn),是不稳定的排序

1.快速排序

快速排序的介绍以及C语言实现在这里：[快速排序C语言实现][C]

本文介绍的是快速排序python实现：

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  def recurse(lista,left,right):
2.  if left<right:
3.  i=left;
4.  j=right;
5.  tmp=lista\[left\];
6.  while(i<j):
7.  while(i<j and lista\[j\]>=tmp):
8.  j=j-1;
9.  if i<j:
10. lista\[i\]=lista\[j\];
11. i=i+1;
12. while (i<j and lista\[i\]<tmp):
13. i=i+1;
14. if i<j:
15. lista\[j\]=lista\[i\];
16. j=j-1;
17. lista\[i\]=tmp;
18. recurse(lista,left,i-1); \#分治
19. recurse(lista,i+1,right);
20. return lista;
21. def quicksort(lista):
22. leng=len(lista);
23. recurse(lista,0,leng-1);
24. 
25. lista=\[1,4,23,45,97,22,10,4\]; \#快速排序测试代码
26. quicksort(lista);
27. print lista;

2.归并排序

归并排序及C语言实现在这里：[归并排序C语言实现][C 1]

本文介绍的是归并排序python实现：

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  def merge(lista,left,mid,right): \# 合并有序数组
2.  i=left;
3.  j=mid+1;
4.  tmp=\[\];
5.  while(i<=mid and j<=right):
6.  if lista\[i\]<= lista\[j\]:
7.  tmp.append(lista\[i\]);
8.  i=i+1;
9.  else:
10. tmp.append(lista\[j\]);
11. j=j+1;
12. while(i<=mid):
13. tmp.append(lista\[i\]);
14. i=i+1;
15. while(j<=right):
16. tmp.append(lista\[j\]);
17. j=j+1;
18. i=0;
19. while(i<right-left+1):
20. lista\[left+i\]=tmp\[i\];
21. i=i+1;
22. def mergerecurse(lista,left,right):
23. if left<right:
24. mid=int((right+left)/2);
25. mergerecurse(lista,left,mid);
26. mergerecurse(lista,mid+1,right);
27. merge(lista,left,mid,right);
28. return lista;
29. def mergesort(lista):
30. leng=len(lista);
31. mergerecurse(lista,0,leng-1);
32. 
33. lista=\[1,4,23,45,97,22,10,4\]; \#测试代码
34. mergesort(lista);
35. print lista;
36.

3.堆排序

堆排序及C语言实现在这里：[堆排序C语言实现][C 2]

本文介绍的是堆排序python实现：

python中提供了堆这种数据结构，可以直接使用heap中的heappush方法来建立堆，使用heappop来弹出堆中的最小元素。

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  from heapq import \*;
2.  def heapsort(lista):
3.  h=\[\];
4.  for i in range(0,len(lista)):
5.  heappush(h,lista\[i\]);
6.  for i in range(0,len(h)):
7.  lista\[i\]=heappop(h);

也可以自行实现heap数据结构：

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  def heapadjust(lista,s,end):
2.  i=2\*s+1;
3.  tmp=lista\[s\];
4.  while(i<=end):
5.  if i+1<=end and lista\[i+1\]>lista\[i\]:
6.  i=i+1;
7.  if lista\[i\]<=tmp:
8.  break;
9.  lista\[s\]=lista\[i\];
10. s=i;
11. i=s\*2\+1;
12. lista\[s\]=tmp;
13. def heapsort2(lista):
14. n=len(lista);
15. for i in range((n-1)/2,-1,-1):
16. heapadjust(lista,i,n-1);
17. for i in range(n-1,-1,-1):
18. lista\[i\],lista\[0\]=lista\[0\],lista\[i\];
19. heapadjust(lista,0,i-1);
20. lista=\[5,4,2,5,1,7\]; \# 堆排序测试代码
21. heapsort(lista);
22. print lista;

[C]: http://blog.csdn.net/u011608357/article/details/20801981
[view plain]: http://blog.csdn.net/u011608357/article/details/37724329#
[C 1]: http://blog.csdn.net/u011608357/article/details/21331529
[C 2]: http://blog.csdn.net/u011608357/article/details/21381701