我正在尝试理解一些排序算法，但我很难看出冒泡排序和插入排序算法的区别。
我知道两者都是O(n2)，但在我看来，冒泡排序仅将数组的最大值冒泡到每次排序的顶部，而插入排序则将最小值下沉到每次排序的底部。它们不是在做完全相同的事情，只是方向不同吗？
对于插入排序，比较/潜在交换的次数从零开始逐渐增加（即0、1、2、3、4、…、n），但对于冒泡排序，这种行为也发生在排序结束时（即n、n-1、n-2、… 0）因为冒泡排序不再需要与已排序的最后一个元素进行比较。
尽管如此，似乎有共识认为插入排序通常更好。有人能告诉我原因吗？
编辑：我主要关注算法工作方式的差异，而不是其效率或渐近复杂度。
经过i次迭代，前i个元素已排序。
在每一次迭代中，下一个元素会在已排序的部分中冒泡，直到到达正确的位置：
sorted | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2
4被冒泡到已排序的部分
伪代码：
for i in 1 to n
for j in i downto 2
if array[j - 1] > array[j]
swap(array[j - 1], array[j])
else
break
经过i次迭代，最后i个元素是最大的，并且已经有序。
在每次迭代中，遍历未排序的部分以找到最大值。
unsorted | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9
5从未排序的部分冒出来了
伪代码：
for i in 1 to n
for j in 1 to n - i
if array[j] > array[j + 1]
swap(array[j], array[j + 1])
请注意，如果在外部循环的迭代过程中没有进行交换，则典型实现会提前终止（因为这意味着数组已经排序）。
在插入排序中，元素被冒泡到已排序部分，而在冒泡排序中，最大值被冒泡到未排序部分之外。
还有一个区别，我在这里没有看到：
冒泡排序 每次交换需要 3 次值赋值： 首先，你必须创建一个临时变量来保存你想要向前推进的值（第 1 步），然后你必须把另一个交换变量写入刚才保存的值所在的位置（第 2 步），最后，你必须将临时变量写入其他位置 (第 3 步)。为了将变量排序到正确的位置，你必须对每个位置执行以上步骤。
使用插入排序，将要排序的变量放入一个临时变量中，并将该变量之前的所有变量都向前移动一位，直到达到变量的正确位置。这使得每个位置只需要进行1次值赋值。最后，将临时变量写入这个位置。
这样做的值赋值次数也少得多。
这不是最大的速度优势，但我认为它值得一提。
希望我表达清晰易懂，如果不是，请原谅，我不是英国本地人。
插入排序的主要优点是它是一种在线算法。你不需要在开始时就拥有所有值。当处理来自网络或某些传感器的数据时，这可能非常有用。
我有一种感觉，这可能比其他传统的 n log(n) 算法更快。因为复杂度会是 n*(n log(n)) ，例如从流中读取/存储每个值 (O(n))，然后对所有值进行排序 (O(n log(n)))，导致 O(n^2 log(n))
相反，使用插入排序仅需 O(n) 从流中读取值和 O(n) 将值放置到正确的位置，因此只需 O(n^2)。另一个优点是，您不需要缓冲区来存储值，可以在最终目的地中对它们进行排序。
O(n log(n))(任何时候的中序遍历复杂度为O(m))。如果只需要最终有序结果，但希望将排序计算与数据传输重叠，则可使用堆排序(可以原地排序，类似于插入排序)。 - Peter CordesO(f(n))复杂度类比实现细节和常数因子更重要的情况，冒泡排序和插入排序都不是理想的选择。 - Peter Cordesn个插入维护一个排序数组，那么它真正取决于哪种算法最适合对几乎排序的数组进行排序，其中顶部有一个未排序的元素。许多O(n log(n))排序算法在几乎排序的情况下是O(n)，因此并不是真的需要sum(M=1..n, O(M * log(M)))工作量。那确实将是O(n^2 log(n))，但是通过选择正确的算法，它们将是总共O(n^2)的工作量。插入排序对此最有效。 - Peter Cordes当有人需要从一大串数字中找出前k个元素时，冒泡排序比插入排序更好。
举例来说，在冒泡排序中，经过k轮迭代后，你就能得到前k个元素。但是在插入排序中，经过k轮迭代后，只能保证这k个元素已经排好序了。
相邻输入。相邻输入。插入排序：
1.在插入排序中，不需要交换。
2.插入排序的时间复杂度为Ω(n)（最佳情况）和O(n^2)（最坏情况）。
3.与冒泡排序相比，插入排序较简单。
4.例如：将书籍插入图书馆，整理卡片。
冒泡排序：
1.在冒泡排序中需要交换。
2.冒泡排序的时间复杂度为Ω(n)（最佳情况）和O(n^2)（最坏情况）。
3.与插入排序相比，冒泡排序更为复杂。
我会尝试给出比其他人更简洁和信息丰富的答案。
是的，在每次排序后，插入排序和冒泡排序直观上看起来相同 - 它们都在边缘构建一个排序子列表。
然而，插入排序通常会执行更少的比较。使用插入排序，我们仅在每次排序中对排序子列表进行线性搜索。对于随机数据，您可以预期进行m/2次比较和交换，其中m是排序子列表的大小。
使用冒泡排序，我们总是在未排序的子列表中比较每一对元素，因此这是n-m次比较（与插入排序在随机数据上相比多两倍）。这意味着如果比较昂贵/慢，则冒泡排序效果不佳。
此外，与插入排序相关的交换和比较的分支更可预测。我们同时进行线性搜索和线性插入，并且通常可以预测/假设线性搜索/插入将继续进行，直到找到正确的位置。使用冒泡排序，分支基本上是随机的，我们可以预期有一半的时间会出现分支错误！每次比较都是如此！这意味着如果比较和交换相对便宜/快速，则冒泡排序对流水线处理器不利。
这些因素使冒泡排序通常比插入排序慢得多。