数据结构定义和算法--排序--冒泡排序
排序原理
- 冒泡排序只会操作相邻的两个数;
- 对相邻的两个数据进行比较,看是否满足大小关系,如果不满足就互换位置;
- 一次冒泡会让至少一个元素交换到它该在的位置,重复n次就完成了排序;
- 优化:若某次冒泡不存在数据互换,就完成了n个数据的排序互换;
性能分析
- 最小时间复杂度:当数据完全有序时,只需进行一次冒泡操作,时间复杂度为O(n);
- 最大时间复杂度:当数据完全逆序时,需要n次冒泡操作,时间复杂度为O(n^2);
- 平均时间复杂度:取个中间值近似(不严谨但很实用)为n*(n-1)/4,复杂度还是O(n^2);
- 空间复杂度:每次互换只需要一个临时变量,故而空间复杂度为O(1),为原地排序算法;
- 算法稳定性:如果两个值相等,就不会交换位置,故而是稳定排序算法;