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

This topic created in 3270 days ago, the information mentioned may be changed or developed.

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

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

排序

冒泡

插入

已排序区

7 replies • 2017-11-24 15:10:02 +08:00

neosfung

Nov 24, 2017

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

coderluan

Nov 24, 2017

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

czheo

Nov 24, 2017

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

czheo

Nov 24, 2017

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

czheo

Nov 24, 2017

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

liuminghao233

Nov 24, 2017 via iPhone

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

blackjar

Nov 24, 2017

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

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

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