首页 文章

插入排序与冒泡排序算法

提问于
浏览 次
58

我正在尝试理解一些排序算法，但我很难看到冒泡排序和插入排序算法的差异 .

我知道两者都是O（n2），但在我看来，冒泡排序只是将每个传递的数组的最大值冒泡到顶部，而插入排序只是将每个传递的最低值下沉到底部 . 他们不是在做同样的事情，而是在不同的方向吗？

对于插入排序，比较/潜在交换的数量从零开始并且每次都增加（即0,1,2,3,4，...，n）但是对于冒泡排序，这种相同的行为发生，但是在结束时排序（即n，n-1，n-2，... 0）因为冒泡排序不再需要与排序后的最后一个元素进行比较 .

尽管如此，似乎一致认为插入排序更好 . 谁能告诉我为什么？

编辑：我主要关注算法如何工作的差异，而不是他们的效率或渐近复杂性 .

algorithm sorting

11 回答

  • 0

    在第i次迭代中的冒泡排序中，你总共有ni-1内迭代（n ^ 2）/ 2，但是在插入排序中，你在第i步上有最大的i次迭代，但平均来说是i / 2，因为你可以停止内部循环之前，在找到当前元素的正确位置之后 . 所以你有（总和0到n）/ 2总共（n ^ 2）/ 4;

    这就是为什么插入排序比冒泡排序更快的原因 .

    回复于
  • -1

    插入排序

    在迭代之后，第一个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元素是最大的，并且是有序的 .

    在每次迭代中，筛选未排序的部分以找到最大值 .

    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])

    请注意，如果在外部循环的一次迭代期间没有进行交换，则典型的实现会提前终止（因为这意味着数组已排序） .

    差异

    在插入中，排序元素被冒泡到已排序的部分，而在冒泡排序中，最大值被排出未排序的部分 .

    回复于
  • 1

    另一个区别，我没有在这里看到：

    Bubble sort 有 3 value assignments per swap ：你必须首先 Build 一个临时变量以保存你想要推进的值（1号），而不是必须将另一个交换变量写入你刚刚保存的值（2号） ）然后你必须在现场其他地点（3号）写你的临时变量 . 你必须为每个点做到这一点 - 你想要前进 - 将你的变量排序到正确的位置 .

    使用 insertion sort ，您可以将变量放入临时变量中，然后将所有变量放在该点之前1点，只要您到达变量的正确位置即可 . 这使 1 value assignement per spot . 最后，你将临时变量写入现场 .

    这也远不是 Value 分配 .

    这不是最强的速度效益，但我认为可以提及 .

    我希望，我表达自己可以理解，如果没有，对不起，我不是英国人

    回复于
  • 28

    冒泡排序不在线（它不能在不知道将有多少项目的情况下对输入流进行排序），因为它并不真正跟踪已排序元素的全局最大值 . 插入项目时，您需要从一开始就开始冒泡

    回复于
  • 92

    插入排序的主要优点是它是在线算法 . 您不必在开始时拥有所有值 . 在处理来自网络或某些传感器的数据时，这可能很有用 .

    我有一种感觉，这会比其他传统的算法更快 . 因为复杂性将是 n*(n log(n)) ，例如从流（ O(n) ）读取/存储每个值，然后对所有值（ O(n log(n)) ）进行排序，得到 O(n^2 log(n))

    相反，使用Insert Sort需要 O(n) 来从流中读取值，而 O(n) 将值放到正确的位置，因此它只是 O(n^2) . 其他优点是，您不需要缓冲区来存储值，您可以在最终目标中对它们进行排序 .

    回复于
  • 0

    只有当某人从一个大的数字列表中寻找前k个元素时才进行冒泡排序比插入排序更好，即在k次迭代后你将获得前k个元素的冒泡排序 . 但是，在插入排序中进行k次迭代后，它只能确保对这些k个元素进行排序 .

    回复于
  • 3

    虽然这两种排序都是O（N ^ 2） . 隐藏常量在插入排序中要小得多 . 隐藏常量是指执行的基本操作的实际数量 .

    插入排序有更好的运行时间？

    • 数组几乎排序 - 注意插入排序在这种情况下比冒泡排序执行的操作更少 .

    • 数组的大小相对较小：插入排序你移动元素，放置当前元素 . 这只比冒泡排序更好元素的数量很少 .

    请注意，插入排序并不总是比冒泡排序更好 . 为了充分利用两个世界，如果数组的大小很小，可以使用插入排序，并且可能为较大的数组合并排序（或快速排序） .

    回复于
  • 14

    在任何情况下，冒泡排序几乎都是无用的 . 在插入排序可能有太多交换的用例中，可以使用选择排序，因为它保证少于N次交换 . 因为选择排序比冒泡排序更好，所以冒泡排序没有用例 .

    回复于
  • 6

    每次迭代中的交换次数

    • 插入排序确实 at most 1 swap in each iteration .

    • Bubble-sort在每次迭代中执行0到n交换 .

    访问和更改已排序的部分

    • 插入 - 排序访问（并在需要时进行更改）已排序的部分以查找考虑的数字的正确位置 .

    • 优化后，Bubble-sort不会访问已排序的内容 .

    在线与否

    • 插入排序在线 . 这意味着插入排序在放入适当位置之前需要 one input at a time . 它不必只比较 adjacent-inputs .

    • 冒泡排序不在线 . 它不能一次操作一个输入 . 它在每次迭代中处理一组输入（如果不是全部） . 在每次迭代中冒泡排序 only compare and swap adjacent-inputs .

    回复于
  • 1

    插入排序：

    1.在插入排序中不需要交换 .

    2.插入排序的时间复杂度对于最佳情况为Ω（n），在最坏情况下为O（n ^ 2） .

    3.与冒泡排序相比，无复杂 .

    4.示例：在图书馆插入书籍，安排卡片 .

    冒泡排序：1 . 冒泡排序需要等待 .

    2.冒泡排序的时间复杂度在最佳情况下为Ω（n），在最坏情况下为O（n ^ 2） .

    3.与插入排序相比更复杂 .

    回复于
  • 6

    插入排序可以恢复为“查找应该位于第一个位置的元素（最小值），通过移动下一个元素来创建一些空间，并将它放在第一个位置 . 好 . 现在看看应该在第二个位置的元素 . ...“ 等等...

    冒泡排序的操作方式不同，可以恢复为“只要我发现两个相邻元素的顺序错误，我就交换它们” .

    回复于

相关问题