选择、插入、冒泡是入门级的排序算法，虽然性能不怎么样，但是属于基础，为后面的排序也提供良好的思路。
三种排序比较
相同点
- 时间复杂度都是 O(n^2)，空间复杂度都是 O(1)。
- 都需要采用两重循环。
不同点
- 选择排序是不稳定的，冒泡排序、插入排序是稳定的；
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 在这三个排序算法中，选择排序交换的次数是最少的；
选择排序
选择排序可以演变为二元选择排序：
- 二元选择排序：一次遍历选出两个值——最大值和最小值；
- 二元选择排序剪枝优化：当某一轮遍历出现最大值和最小值相等，表示数组中剩余元素已经全部相等。
插入排序
插入排序有两种写法：
- 交换法：新数字通过不断交换找到自己合适的位置；
- 移动法：旧数字不断向后移动，直到新数字找到合适的位置。
冒泡排序
冒泡排序有两种优化方式：
- 记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序；
- 记录上次发生交换的位置，下一轮排序时只比较到此位置。
网友评论