选择排序、插入排序、冒泡排序python实现
选择排序的时间复杂度为O(n^2),是不稳定的排序
冒泡排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),平均情况下为O(n^2),是稳定的排序
插入排序的时间复杂度最好情况下为O(n),最坏情况下为O(n^2),,平均情况下为O(n^2),是稳定的排序
1.选择排序
def selection(lista):
leng=len(lista);
for i in range(0,leng):
index=i;
min=lista[i];
for j in range(i,leng):
if lista[j]<min:
index=j;
min=lista[index];
tmp=lista[i];
lista[i]=lista[index];
lista[index]=tmp;
return lista;2.插入排序
def insertion(lista):
leng=len(lista);
for i in range(1,leng):
tmp=lista[i];
j=i;
while(j>0 and lista[j-1]>tmp):
lista[j]=lista[j-1];
j=j-1;
lista[j]=tmp;
return lista;3.冒泡排序
def bubble(lista):
leng=len(lista);
for i in range(0,leng):
for j in range(1,leng-i):
if lista[j-1]>lista[j]:
lista[j-1],lista[j]=lista[j],lista[j-1];
return lista;4.冒泡排序的改进
假设在某趟排序后数组已经有序，则排序完毕。
def bubble2(lista):
leng=len(lista);
flag=True;
while(flag):
flag=False;
for i in range(0,leng):
for j in range(1,leng-i):
if lista[j-1]>lista[j]:
lista[j-1],lista[j]=lista[j],lista[j-1];
flag=True;
return lista;測试排序的代码：
lista=[5,3,1,4,7,9,8,2,6];
selection(lista); #选择排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
insertion(lista); #插入排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
bubble(lista); #冒泡排序
print lista
lista=[5,3,1,4,7,9,8,2,6];
bubble2(lista); #冒泡排序改进
print lista发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/119010.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021年11月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读