前三种总结

时间复杂度乍一看，好像插入排序速度还不慢，但是要知道： 当序列正好逆序的时候，每次插入都要一次次交换，这个速度和冒泡排序是一样的，时间复杂度O(n²)； 当然运气好，前面是有序的，那时间复杂度就只有O(n)了，直接插入即可。

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
冒泡排序	O(n²)	O(n²)	O(1)	是
选择排序	O(n²)	O(n²)	O(1)	不是
直接插入排序	O(n²)	O(n²)	O(1)	是

好了，这张表如何快速记忆呢？ 方法就是一开始写的基本排序算法 。 一开始就说到，基本思想就是两层循环嵌套，第一遍找元素O(n),第二遍找位置O(n)，所以这几种方法，时间复杂度就可以这么简便记忆啦! 作者：Vincent Ko 链接：https://juejin.im/post/5b72f0caf265da282809f3b5 来源：掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。