DAA 冒泡排序

冒泡排序，也称为交换排序，是一种简单的排序算法。它的工作原理是重复地遍历要排序的列表，一次比较两个项目，如果它们的顺序错误则交换它们。对列表的遍历会重复进行，直到不需要交换为止，这意味着列表已排序。

这是所有排序算法中最简单的方法。

算法

步骤 1 ➤ 初始化

步骤 2 ➤ 循环，

步骤 3 ➤ 比较，循环。

步骤 4 ➤ 完成，或减小大小。

冒泡排序的工作原理

1. 冒泡排序从第一个索引开始，并将其设为冒泡元素。然后它将冒泡元素（当前是我们的第一个索引元素）与下一个元素进行比较。如果冒泡元素较大，第二个元素较小，则两者将交换。
   交换后，第二个元素将成为冒泡元素。现在我们将像上一步一样比较第二个元素与第三个元素，并在必要时交换它们。重复相同的过程，直到最后一个元素。
2. 我们将对其余的迭代重复相同的过程。在每次迭代之后，我们会注意到，未排序数组中最大的元素已经到达最后一个索引。

对于每次迭代，冒泡排序将最多比较到最后一个未排序的元素。

一旦所有元素都按升序排序，算法将终止。

考虑以下我们将在冒泡排序算法的帮助下排序的未排序数组的示例。

最初，

第 1 轮

• 比较 a₀ 和 a₁

由于 a₀ < a₁，因此数组将保持不变。

• 比较 a₁ 和 a₂

现在 a₁ > a₂，因此我们将交换它们。

• 比较 a₂ 和 a₃

由于 a₂ < a₃，因此数组将保持不变。

• 比较 a₃ 和 a₄

这里 a₃ > a₄，因此我们将再次交换它们。

第 2 轮

• 比较 a₀ 和 a₁

由于 a₀ < a₁，因此数组将保持不变。

• 比较 a₁ 和 a₂

这里 a₁ < a₂，因此数组将保持不变。

• 比较 a₂ 和 a₃

在这种情况下，a₂ > a₃，因此它们将交换。

第 3 轮

• 比较 a₀ 和 a₁

由于 a₀ < a₁，因此数组将保持不变。

• 比较 a₁ 和 a₂

现在 a₁ > a₂，因此它们将交换。

第 4 轮

• 比较 a₀ 和 a₁

这里 a₀ > a₁，因此我们将交换它们。

因此，数组已排序，因为不需要再进行交换。

冒泡排序的复杂度分析

输入： 给定 n 个输入元素。

输出： 对列表进行排序所需的步骤数。

逻辑： 如果给定 n 个元素，则在第一轮中，它将进行 n-1 次比较；在第二轮中，它将进行 n-2 次比较；在第三轮中，它将进行 n-3 次比较，依此类推。因此，可以通过以下方式找到总的比较次数；

因此，冒泡排序算法包含 O(n²) 的时间复杂度和 O(1) 的空间复杂度，因为它需要一些用于交换的 temp 变量的额外内存空间。

时间复杂度

• 最佳情况复杂度：冒泡排序算法对于已排序的数组具有 O(n) 的最佳时间复杂度。
• 平均情况复杂度：冒泡排序算法的平均时间复杂度为 O(n²)，当 2 个或更多个元素混在一起时发生，即既不是升序也不是降序。
• 最坏情况复杂度：最坏情况时间复杂度也是 O(n²)，当我们对数组的降序进行升序排序时发生。

冒泡排序的优点

1. 容易理解。
2. 不需要任何额外的内存。
3. 可以轻松地为该算法编写代码。
4. 比其他排序算法需要更少的空间。

冒泡排序的缺点

1. 当我们有大型未排序列表时，它无法很好地工作，并且它需要更多资源，最终需要花费大量时间。
2. 它仅用于学术目的，不用于实际实现。
3. 它涉及 n² 阶的步骤来排序算法。