选择排序、插入排序、冒泡排序python实现

红太狼 2022-07-17 02:52 199阅读 0赞

选择排序的时间复杂度为O(n^2),是不稳定的排序

冒泡排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),平均情况下为O(n^2),是稳定的排序

插入排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),,平均情况下为O(n^2),是稳定的排序

1.选择排序

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

1.  def selection(lista):
2.  leng=len(lista);
3.  for i in range(0,leng):
4.  index=i;
5.  min=lista\[i\];
6.  for j in range(i,leng):
7.  if lista\[j\]<min:
8.  index=j;
9.  min=lista\[index\];
10. tmp=lista\[i\];
11. lista\[i\]=lista\[index\];
12. lista\[index\]=tmp;
13. return lista;

2.插入排序

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

1.  def insertion(lista):
2.  
3.  leng=len(lista);
4.  for i in range(1,leng):
5.  tmp=lista\[i\];
6.  j=i;
7.  while(j>0 and lista\[j-1\]>tmp):
8.  lista\[j\]=lista\[j-1\];
9.  j=j-1;
10. lista\[j\]=tmp;
11. return lista;

3.冒泡排序

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

1.  def bubble(lista):
2.  leng=len(lista);
3.  for i in range(0,leng):
4.  for j in range(1,leng-i):
5.  if lista\[j-1\]>lista\[j\]:
6.  lista\[j-1\],lista\[j\]=lista\[j\],lista\[j-1\];
7.  return lista;

4.冒泡排序的改进

如果在某趟排序后数组已经有序，则排序完成。

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

1.  def bubble2(lista):
2.  leng=len(lista);
3.  flag=True;
4.  while(flag):
5.  flag=False;
6.  for i in range(0,leng):
7.  for j in range(1,leng-i):
8.  if lista\[j-1\]>lista\[j\]:
9.  lista\[j-1\],lista\[j\]=lista\[j\],lista\[j-1\];
10. flag=True;
11. return lista;

测试排序的代码：

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

1.  lista=\[5,3,1,4,7,9,8,2,6\];
2.  selection(lista); \#选择排序
3.  print lista
4.  lista=\[5,3,1,4,7,9,8,2,6\];
5.  insertion(lista); \#插入排序
6.  print lista
7.  lista=\[5,3,1,4,7,9,8,2,6\];
8.  bubble(lista); \#冒泡排序
9.  print lista
10. lista=\[5,3,1,4,7,9,8,2,6\];
11. bubble2(lista); \#冒泡排序改进
12. print lista

[view plain]: http://blog.csdn.net/u011608357/article/details/37722107#