Java 中的冒泡排序

冒泡排序算法是计算机科学中最简单的排序算法之一。它重复地遍历列表，比较相邻的元素，如果它们的顺序不对就交换它们。这个过程会一直持续到列表被排序。它的名字来源于较小的元素如何“冒泡”到列表的顶部。它不适用于大型数据集。

冒泡排序主要用于

• 不关心复杂度
• 偏爱简单且简短的代码

以下是分步解释

• 比较相邻元素：从第一个元素开始。将其与下一个元素进行比较。
• 必要时交换：如果当前元素大于下一个元素，则交换它们。
• 对所有对重复：对列表中的所有相邻元素执行此操作。第一遍之后，最大的元素将“冒泡”到其正确的位置。
• 忽略已排序的最后一个元素：对剩余未排序的元素重复此过程，忽略最后一个已排序的元素。
• 未进行交换时停止：如果在完整的一遍中没有进行任何交换，则列表已排序。

算法

冒泡排序的步骤

步骤 1：比较输入数组的前两个元素。

步骤 2：如果第一个元素大于第二个元素，则交换它们；否则，不需要交换。

步骤 3：根据步骤 2，对输入数组的下一对元素（第二个和第三个元素）进行比较和交换，即，如果第二个元素大于第三个元素，则交换；否则，不交换。

步骤 4：一直继续这个过程直到到达输入数组的末尾。此时，最大的元素将“冒泡”到列表的末尾。

步骤 5：重复步骤 1 到 4，不包括最后一个元素，因为它已经处于其正确位置。

冒泡排序算法的工作原理

我们已将以下数组作为输入数组。

第一次遍历

比较前两个元素。我们看到第一个元素小于第二个元素。因此，不需要交换。

之后，比较第二个元素和第三个元素。观察到第二个元素大于第三个元素。因此，交换元素 16 和 11。

交换后，比较第三个元素和第四个元素。观察到第三个元素大于第四个元素。因此，交换元素 16 和 13。

交换后，比较第四个元素和第五个元素。我们看到第四个元素大于第五个元素。因此，交换元素 16 和 14。

此时，我们已将数组中的最大元素放在已排序数组中的正确位置（末尾）。

再次，比较前两个元素。我们看到第一个元素大于第二个元素。因此，交换元素 15 和 11。

第二次遍历

之后，比较第二个元素和第三个元素。观察到第二个元素大于第三个元素。因此，交换元素 15 和 13。

交换后，比较第三个元素和第四个元素。观察到第三个元素大于第四个元素。因此，交换元素 15 和 14。

此时，我们已将两个元素放在已排序数组中的正确位置。这两个元素分别是数组中最大和第二大的元素。

第三次遍历

再次，比较前两个元素。我们看到第一个元素小于第二个元素。因此，不需要交换。

之后，比较第二个元素和第三个元素。观察到第二个元素小于第三个元素。因此，不需要交换。

由于没有进行交换，因此不需要进一步检查，因为数组已排序。

Java 中冒泡排序的实现

输出

Before sorting array elements are: 
15 16 11 13 14
After sorting array elements are: 
11 13 14 15 16

复杂度分析

让我们看看冒泡排序在最佳情况、平均情况和最坏情况下的时间和空间复杂度。

时间复杂度

最佳情况复杂度：当不需要排序时发生，即数组已排序。冒泡排序的最佳情况时间复杂度为O(n)。

平均情况复杂度：当数组元素以一种混乱的顺序排列时发生，既不是升序也不是降序。冒泡排序的平均情况时间复杂度为O(n²)。

最坏情况复杂度：当数组元素需要按相反顺序排序时发生。这意味着需要按升序对数组元素进行排序，但其元素却是降序的。冒泡排序的最坏情况时间复杂度为O(n²)。

空间复杂度

冒泡排序的空间复杂度为 O(1)。因为在冒泡排序中，需要一个额外的变量来进行交换。

冒泡排序的应用

• 教学工具：冒泡排序是一种直接的算法。因此，它适用于向初学者教授排序基础知识。
• 接近排序的数据：当数据接近排序时，冒泡排序效果很好，因为它能快速发现并修复微小的错位。

冒泡排序的优点

• 易于实现和理解。
• 不需要额外的内存空间。
• 它是一种稳定的排序算法。这意味着在已排序的输出中，具有相同键值的元素会保持其相对顺序。

冒泡排序的缺点

• 冒泡排序对于大型数据集来说很慢，因为它具有 O(n²) 的时间复杂度。
• 实际应用中，冒泡排序的应用为零或非常有限。它通常用于学术界教授各种排序方法。

结论

冒泡排序算法是一种可靠的排序算法，易于理解。它通过反复比较和交换相邻的元素，直到整个数组被排序。

Java 冒泡排序选择题

1. 冒泡排序在平均情况下的时间复杂度是多少？

1. O(n)
2. O(n log n)
3. O(n²)
4. O(log n)

2. 冒泡排序的主要缺点是什么？

1. 它不稳定
2. 它使用过多的内存
3. 它具有高时间复杂度
4. 它无法处理大型数据集

3. 以下关于冒泡排序的陈述哪一项是正确的？

1. 它总是比快速排序表现更好。
2. 它是一种稳定的排序算法。
3. 它需要额外的内存进行排序。
4. 它是一种递归算法。

4. 冒泡排序如何处理已排序的数组？

1. 它执行 n^2 次比较。
2. 它不执行任何比较。
3. 它执行 n 次比较。
4. 它执行 n-1 次比较。

5. 哪种技术可以用来提高冒泡排序的性能？

1. 动态规划
2. 记忆化
3. 提前退出
4. 二分搜索