我正在尝试理解一些排序算法,但我很难看出冒泡排序和插入排序算法的区别。
我知道两者都是O(n2),但在我看来,冒泡排序仅将数组的最大值冒泡到每次排序的顶部,而插入排序则将最小值下沉到每次排序的底部。它们不是在做完全相同的事情,只是方向不同吗?
对于插入排序,比较/潜在交换的次数从零开始逐渐增加(即0、1、2、3、4、…、n),但对于冒泡排序,这种行为也发生在排序结束时(即n、n-1、n-2、… 0)因为冒泡排序不再需要与已排序的最后一个元素进行比较。
尽管如此,似乎有共识认为插入排序通常更好。有人能告诉我原因吗?
编辑:我主要关注算法工作方式的差异,而不是其效率或渐近复杂度。