选择排序的时间复杂度为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]

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 listalista=[5,3,1,4,7,9,8,2,6];insertion(lista);      #插入排序print listalista=[5,3,1,4,7,9,8,2,6];bubble(lista);        #冒泡排序print listalista=[5,3,1,4,7,9,8,2,6];bubble2(lista);        #冒泡排序改进print lista