插入sorting与气泡sortingalgorithm
我想了解一些sortingalgorithm，但我很努力看到气泡sorting和插入sortingalgorithm的区别。
我知道两者都是O（n 2 ），但在我看来，冒泡sorting只是将数组的最大值冒泡到每个传递的顶部，而插入sorting只是将最低值沉入每个传递的底部。 他们是不是在做同样的事情，但方向不一样？
对于插入sorting，比较/潜在互换的次数从零开始并且每次增加（即，0,1,2,3,4，…，n），但是对于气泡sorting，这种相同的行为发生，但是在sorting（即n，n-1，n-2，… 0），因为冒泡sorting不再需要与sorting后的最后一个元素进行比较。
尽pipe如此，插入sorting总体来说似乎是一个共识。 谁能告诉我为什么？
编辑： 我主要关心algorithm如何工作的差异，而不是他们的效率或渐近的复杂性。
在第i次迭代的气泡sorting中，您有ni-1个内部迭代（n ^ 2）/ 2个总数，但是在插入sorting中，您可以在第i个步骤中获得最大迭代次数，但平均为i / 2，因为您可以停止内部循环之前，在为当前元素find正确位置之后。 所以你有（总和从0到n）/ 2总共是（n ^ 2）/ 4;
这就是插入sorting比泡泡sorting更快的原因。
插入sorting
在迭代之后，第一个元素被sorting。
在每次迭代中，下一个元素都会通过已sorting的部分冒泡，直到到达正确的位置：
sorted | unsorted 1 3 5 8 | 4 6 7 9 2 1 3 4 5 8 | 6 7 9 2 4被冒泡到sorting部分
伪代码：
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
泡沫sorting
在我迭代后，最后一个元素是最大的，并下令。
在每次迭代中，筛选未sorting的部分以查找最大值。
unsorted | biggest 3 1 5 4 2 | 6 7 8 9 1 3 4 2 | 5 6 7 8 9
5从未sorting的部分冒出来
伪代码：
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])
请注意，如果在外循环的一次迭代过程中没有进行交换（因为这意味着数组已被sorting），典型的实现会提前终止。
区别
在插入中，sorting元素会冒泡到sorting的部分，而在冒泡sorting中，最大值会从未sorting的部分冒出来。
另一个区别，我没有在这里看到：
泡泡sorting有3个值分配每个交换 ：你必须先build立一个临时variables来保存你想要推进的值（1号），比你必须将另一个交换variables写入你刚才保存的值（2号），然后你必须写在你的临时variables在现货其他点（3号）。 你必须为每个点做这个 – 你想要前进 – 把你的variables分类到正确的位置。
通过插入sorting，您可以将您的variablessorting到一个临时variables中，然后将所有variables放在该点的前面1个点，只要您到达variables的正确位置即可。 这使得每个点有1个值分配 。 最后，你写你的临时variables到现场。
这也使得价值分配远远不够。
这不是最强的速度效益，但我认为可以提到。
我希望，我expression了自己的理解，如果不是的话，对不起，我不是英国人
Bubble Sort不在线（它不能在不知道有多less项目的情况下对inputstream进行sorting），因为它没有真正跟踪sorting元素的全局最大值。 插入物品时，您需要从头开始冒泡
插入sorting的主要优点是它是在线algorithm。 你不必在开始时拥有所有的值。 在处理来自networking或某个传感器的数据时，这可能很有用。
我有一种感觉，这将比其他传统的n log(n)algorithm更快。 因为复杂度是n*(n log(n))例如从stream（ O(n) ）中读取/存储每个值，然后对所有的值（ O(n log(n)) ）进行sorting， O(n^2 log(n))
相反，使用Insert Sort需要O(n)用于读取stream中的值，而O(n)需要将该值放到正确的位置，因此它只是O(n^2) 。 其他的好处是，你不需要缓冲区来存储值，你可以将它们分类到最终目的地。
好的气泡sorting比插入sorting要好，只有当有人从数字的大列表中寻找最前面的k个元素时，比如在k次迭代之后的气泡sorting中，你会得到最前面的k个元素。 但是，在插入sortingk次迭代之后，它只能确保这些k元素被sorting。
虽然这两种sorting都是O（N ^ 2），隐式常量在插入sorting中要小得多。隐式常量是指实际执行的基本操作的数量。
插入sorting有更好的运行时间？
- 数组几乎是sorting的 – 注意插入sorting在这种情况下执行的操作比泡泡sortingless。
- 数组的大小相对较小：插入sorting可以将元素移动到当前元素的周围。如果元素数量很less，这只会比冒泡sorting更好。
注意插入sorting并不总是比冒泡sorting更好。为了获得两全其美的效果，如果数组的大小很小，可以使用插入sorting，并且可能会将sorting（或快速sorting）合并到较大的数组中。
在任何情况下泡沫sorting都是无用的。 在插入sorting可能具有太多交换的使用情况下，可以使用selectsorting，因为它保证less于N次交换。 由于selectsorting比冒泡sorting好，冒泡sorting没有用例。
插入sorting可以恢复为“ 查找应该在第一个位置的元素（最小值），通过移动下一个元素来创build一些空间，并把它放在第一个位置。好，现在看看应该在第二个元素。 … “等等…
泡泡sorting的操作有所不同，可以恢复为“ 只要我find两个相邻的元素错误的顺序，我把它们交换 ”。
