冒泡排序和插入排序有什么区别

什么是冒泡排序

冒泡排序是最简单的排序算法。该算法通过一次比较相邻对来对元素进行排序。

考虑以下示例：

40 30 10 70 50 20 60

在冒泡排序中，我们比较相邻元素。

首先，我们考虑 40 和 30。30 小于 40。因此，我们可以交换这两个数字。

30 40 10 70 50 20 60

现在，我们可以考虑 40 和 10。10 小于 40。因此，我们可以交换这两个数字。

30 10 40 70 50 20 60

现在，我们可以考虑 40 和 70。由于 70 大于 40，因此不需要交换数字。

接下来，我们考虑 70 和 50。50 小于 70。因此，我们可以交换这两个数字。

30 10 40 50 70 20 60

然后，我们可以考虑 70 和 20。由于 20 小于 70，我们可以交换这两个元素。

30 10 40 50 20 70 60

现在，我们可以考虑 70 和 60。60 小于 70。因此，我们必须交换这两个数字。

30 10 40 50 20 60 70

现在，您可以看到数据集中最大的元素现在位于末尾。换句话说，在第一遍结束时，最大的元素已经排序。因此，下一次，我们不必考虑 70，因为它已经排序。我们只需要检查其他六个元素。

10 30 40 50 20 60 70

现在，我们考虑 30 和 40。40 大于 30。不需要交换数字。那么，我们可以考虑40和50。由于50大于40，所以不需要交换。

现在，考虑 50 和 20。20 小于 50。因此，我们交换这两个数字。

10 30 40 20 50 60 70

现在，考虑 50 和 60。不需要交换。在第二遍结束时，对第二大元素进行排序。换句话说，60 和 70 现在已排序。该过程一直持续到对所有元素进行排序。

什么是插入排序

插入排序算法通过一次将一个元素传输到部分排序的数组来对数据集进行排序。因此，这种排序算法的开销很低。

考虑以下示例：

40 30 10 70 50 20 60

我们将 40 视为部分排序数组。当我们考虑 30 时，它小于 40。所以我们交换它们。然后，我们考虑 30 和 40 在部分排序的数组中。

30 40 10 70 50 20 60

现在，我们考虑 10。10 小于 30。因此，我们将元素放置如下。 10、30 和 40 在部分排序的数组中。

10 30 40 70 50 20 60

现在，我们考虑 70。它大于 40，因此不需要任何移动。 10, 30, 40, 70 在部分排序的数组中。

现在，考虑 50。它小于 70 但大于 40。我们可以将它们放在正确的位置。 10、30、40、50、70 现在在部分排序的数组中。

10 30 40 50 70 20 60

现在，考虑 20。它大于 10 但小于 20。我们可以将它放在正确的位置。 10, 20, 30, 40, 50, 70 在部分排序的数组中。

10 20 30 40 50 70 60

考虑60，它小于70但大于50，我们可以把它放在正确的位置。

10 20 30 40 50 60 70

现在，我们可以看到所有元素都已排序。在这里，插入排序中的交换次数被最小化，但比较次数仍然很高。

冒泡排序和插入排序的区别

定义

冒泡排序是一种简单的排序算法，它反复遍历一个列表，比较相邻的对，如果它们的顺序错误则交换它们。另一方面，插入排序是一种简单的排序算法，它通过一次传输一个元素来构建最终的排序列表。因此，这是冒泡排序和插入排序之间的主要区别。

功能

冒泡排序检查相邻元素并相应地交换它们，而插入排序一次将一个元素转移到部分排序的数组中。

掉期次数

此外，交换次数是冒泡排序和插入排序之间的重要区别。与冒泡排序相比，插入排序的交换次数更少。

速度

复杂

冒泡排序和插入排序的另一个区别是插入排序比冒泡排序更复杂。

结论

冒泡排序和插入排序适用于对小数据集进行排序。与其他高级排序算法（例如快速排序和归并排序）相比，两者的效率都较低。冒泡排序和插入排序的主要区别在于，冒泡排序通过检查相邻数据元素并在它们的顺序错误时交换它们来执行排序，而插入排序通过一次将一个元素转移到部分排序的数组中来执行排序。

参考：

1.“冒泡排序”。维基百科，维基媒体基金会，2019 年 4 月 15 日，可在此处获取。 2.“插入排序”。维基百科，维基媒体基金会，2019 年 2 月 3 日，可在此处获取。 3.“什么是插入排序？ – 来自 Techopedia 的定义。” Techopedia.com，可在此处获得。

图片提供：

1.1.”2816806”（CC0）来自Pixabay