冒泡排序和插入排序 是不是实际上区别不大？

[lhx2008]

我能想到的两个区别：
1. 插入排序是从靠近 已排序区 的一端开始排，冒泡排序是从远离 已排序区 的一端开始排
2. 待排序的元素 到达指定的位置后，插入排序 不再继续检查，冒泡排序 仍然继续检查到尾端

如果：
冒泡排序如果手动指定一个 flag 变量，使到达位置后不再检查，
那么，是不是可以说两个排序除了第一个微小的区别以外，基本没有区别？

[neosfung]

是的
冒泡其实就是插入排序的一种变种，实现方式不一样而已

[coderluan]

冒泡排序和插入排序的算法复杂度是一样的，所以在我眼中，他们根本没区别......

[czheo]

差别挺大的啊。
最大区别：冒泡时在 [未排序的部分] 里面找最大（或小），放到一端。插入是往 [已排序好] 的部分里面插入当前数。
不变条件(invarient)不同：冒泡是，最大的数会先被排序好到一端。插入是，当前点的一侧是已排序的（ sorted ），这些数并不一定是最大的。
循环终止条件不同：冒泡必须遍历未排序的所有数字才能找到最大，插入找到合适位置就可以停。

[czheo]

之前我总结的： https://medium.com/@czheo/%E6%8E%92%E5%BA%8F-b5ef06533b11。直接看 O(n^2)排序部分。

[czheo]

@czheo 楼上链接坏了： https://medium.com/@czheo/%E6%8E%92%E5%BA%8F-b5ef06533b11

[liuminghao233]

升级版希尔排序可能会好一些

[blackjar]

冒泡跟选择差别不大才对吧 插入就是另外一种思路了
冒泡跟选择都会把待排序列中最大或者最小值每次排出 插入则不是
另外冒泡在每个单元操作中都要交换一次 而选择通常只是对 flag 的位置赋值一次(所以冒泡通常会更慢)
当然这三种都是 O(n2)的排序 这个是一样的。