我试图理解一些排序算法，但我很难看到冒泡排序和插入排序算法的区别。
我知道两者都是 O(n 2 )，但在我看来，冒泡排序只是将数组的最大值冒泡到每次传递的顶部，而插入排序只是将最低值下降到每次传递的底部。他们不是在做同样的事情，但方向不同吗？
对于插入排序，比较/潜在交换的数量从零开始，并且每次都增加（即 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])
请注意，如果在外循环的迭代之一期间没有进行交换，典型的实现会提前终止（因为这意味着数组已排序）。
在插入排序中，元素冒泡进入已排序部分，而在冒泡排序中，最大值从未排序部分冒泡。
在第 i 次迭代中的冒泡排序中，您总共有 ni-1 次内部迭代 (n^2)/2，但在插入排序中，您在第 i 步有最大 i 次迭代，但平均为 i/2，因为您可以停止内部循环早些时候，在您找到当前元素的正确位置之后。所以你有 (sum from 0 to n) / 2 是 (n^2) / 4 总数；
这就是插入排序比冒泡排序快的原因。
另一个区别，我在这里没有看到：
冒泡排序每个交换有3 个值分配：您必须先构建一个临时变量来保存要向前推进的值（第 1 个），而不是必须将另一个交换变量写入刚刚保存值的位置of(no.2) 然后你必须在其他点 (no.3) 中写入临时变量。你必须为每个点都这样做——你想继续前进——将你的变量排序到正确的点。
使用插入排序，您可以将要排序的变量放入临时变量中，然后将所有变量放在该点之前的 1 个点，只要您到达变量的正确点即可。这使得每个点 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)只是。另一个优点是，您不需要缓冲区来存储值，您可以在最终目的地对它们进行排序。
冒泡排序不在线（它无法在不知道有多少项目的情况下对输入流进行排序），因为它并没有真正跟踪已排序元素的全局最大值。插入项目时，您需要从一开始就开始冒泡
只有当有人从大量数字列表中寻找前 k 个元素时，冒泡排序才比插入排序好，即在 k 次迭代后的冒泡排序中，您将获得前 k 个元素。然而，在插入排序的 k 次迭代之后，它只确保那些 k 元素被排序。
虽然这两种排序都是 O(N^2)。插入排序中隐藏的常数要小得多。隐藏常数是指实际执行的原始操作数。
什么时候插入排序有更好的运行时间？
请注意，插入排序并不总是比冒泡排序更好。为了两全其美，如果数组较小，您可以使用插入排序，并且可能对较大的数组使用合并排序（或快速排序）。
adjacent-inputs。adjacent-inputs冒泡排序在所有情况下几乎都是无用的。在插入排序可能有太多交换的用例中，可以使用选择排序，因为它保证少于 N 次交换。因为选择排序比冒泡排序好，所以冒泡排序没有用例。
插入排序：
1.在插入排序中不需要交换。
2.插入排序的时间复杂度最好是Ω(n)，最坏情况是O(n^2)。
3.与冒泡排序相比不太复杂。
4.示例：在图书馆插入书籍，整理卡片。
冒泡排序： 1.冒泡排序需要交换。
2.冒泡排序的时间复杂度最好是Ω(n)，最坏情况是O(n^2)。
3.与插入排序相比更复杂。
我将尝试给出比其他人更简洁和翔实的答案。
是的，在每次遍历之后，插入排序和冒泡排序在直观上看起来是一样的——它们都在边缘构建了一个排序的子列表。
但是，插入排序通常会执行较少的比较。使用插入排序，我们只在每次遍历的排序子列表中执行线性搜索。对于随机数据，您可以期望进行 m/2 比较和交换，其中 m 是已排序子列表的大小。
使用冒泡排序，我们总是在每次遍历时比较未排序子列表中的每一对，所以这是 nm 比较（是随机数据上插入排序的两倍）。这意味着如果比较昂贵/缓慢，则冒泡排序很糟糕。
此外，与插入排序的交换和比较相关的分支更可预测。我们在进行线性插入的同时进行线性搜索，我们通常可以预测/假设线性搜索/插入将继续进行，直到找到正确的空间。使用冒泡排序，分支本质上是随机的，我们可以预期分支会丢失一半！与每一个比较！这意味着如果比较和交换相对便宜/快速，则冒泡排序对流水线处理器不利。
这些因素使冒泡排序通常比插入排序慢得多。
插入排序可以恢复为“寻找应该在第一个位置（最小值）的元素，通过移动下一个元素来腾出一些空间，然后把它放在第一个位置。很好。现在看看应该在第二个的元素。 …… ”等等……
冒泡排序的操作方式不同，可以恢复为“只要我找到两个顺序错误的相邻元素，我就交换它们”。