python实现排序

排序

1）定义

将元素按照某种顺序排列的过程

2）算法好坏衡量指标

1）时间复杂度
将每一步操作看成基本计算单位，解决问题所需的步骤数.
“计算工作量”、“进本运算次数”

2）空间复杂度
执行算法所需要的存储空间，包括：输入数据所占空间、程序本身所占空间、算法执行过程需要的额外空间
这里，我们只考虑完成排序所需要的额外辅助空间

3）稳定性
对序列中两个相同的关键字：
若在初始序列和最终序列中的相对位置不发生变化，则称该排序是稳定的。
若在初始序列和最终序列中的相对位置发生改变，则称该排序时不稳定的。

4）总的比较次数 + 总的交换次数

1、冒泡排序

1）思路分析

多次遍历列表。比较相邻的两个元素，将不符合顺序的进行交换。每一轮便利都将下一个最大值放到正确的位置。

本质：不断消除列表的逆序

2）代码实现

def bubbleSort(alist):
	for i in range(len(alist) - 1):   # 外层循环表遍历了多少轮
		for j in range(1, len(alist) - i):   # 前面的元素两两比较交换
			if alist[j-1] > alist[j]:
				alist[j-1], alist[j] = alist[j-1], alist[j]
	return alist
1
2
3
4
5
6

3）算法分析

1）是稳定排序
2）时间复杂度：O(n²)
3）空间复杂度：O(1)

2、选择排序

1）思路分析

依次找到当前列表中的最小（最大）元素，并将其