O(n^2)

本章我们介绍了三种基础排序算法：冒泡排序、选择排序、插入排序。

冒泡排序

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

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

选择排序

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

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

插入排序

插入排序有两种写法：

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

不同点

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

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

在数组几乎有序的情况下，插入排序的时间复杂度接近线性级别。