选择排序的时间复杂度为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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119010.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...