O(n^2) 排序算法（选择、插入、冒泡）

选择、插入、冒泡是入门级的排序算法，虽然性能不怎么样，但是属于基础，为后面的排序也提供良好的思路。

三种排序比较

相同点

• 时间复杂度都是 O(n^2)，空间复杂度都是 O(1)。
• 都需要采用两重循环。

不同点

• 选择排序是不稳定的，冒泡排序、插入排序是稳定的；

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

• 在这三个排序算法中，选择排序交换的次数是最少的；

选择排序

选择排序可以演变为二元选择排序：

• 二元选择排序：一次遍历选出两个值——最大值和最小值；
• 二元选择排序剪枝优化：当某一轮遍历出现最大值和最小值相等，表示数组中剩余元素已经全部相等。

插入排序

插入排序有两种写法：

• 交换法：新数字通过不断交换找到自己合适的位置；
• 移动法：旧数字不断向后移动，直到新数字找到合适的位置。

冒泡排序

冒泡排序有两种优化方式：

• 记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序；
• 记录上次发生交换的位置，下一轮排序时只比较到此位置。