DSA 冒泡排序

冒泡排序

冒泡排序是一种算法，它将数组从最小值排序到最大值。

运行模拟以查看冒泡排序算法对一组数值数组进行排序时的外观。数组中的每个值都用一列表示。

“冒泡”这个词来自该算法的工作原理，它使最大值“冒泡”到数组的末尾。

继续阅读以完全理解冒泡排序算法以及如何自己实现它。

手动遍历

在用编程语言实现冒泡排序算法之前，让我们手动遍历一个短数组一次，仅仅是为了了解其思路。

**步骤 1：** 我们从一个未排序的数组开始。

**步骤 2：** 我们查看前两个值。最小值是否排在最前面？是的，所以我们不需要交换它们。

**步骤 3：** 向前走一步，查看值 12 和 9。最小值是否排在最前面？否。

**步骤 4：** 因此我们需要交换它们，使 9 排在最前面。

**步骤 5：** 向前走一步，查看 12 和 11。

**步骤 6：** 我们必须交换它们，使 11 排在 12 之前。

**步骤 7：** 查看 12 和 3，我们需要交换它们吗？是的。

**步骤 8：** 交换 12 和 3，使 3 排在最前面。

运行下面的模拟以查看上述 8 个步骤的动画

手动遍历：发生了什么？

我们必须理解在第一次遍历中发生了什么，才能完全理解该算法，以便我们能够用编程语言实现该算法。

你能看到最大值 12 发生了什么吗？它已经“冒泡”到数组的末尾，它应该在那里。但数组的其余部分仍然未排序。

所以冒泡排序算法必须再次遍历数组，一次又一次，每次下一个最大值“冒泡”到它应该的位置。排序继续进行，直到最小值 3 留在数组的开头。这意味着我们需要遍历数组 4 次，才能对包含 5 个值的数组进行排序。

而且每次算法遍历数组时，数组中未排序的部分都会变短。

这就是完整的手动遍历过程

现在，我们将使用我们学到的知识用编程语言实现冒泡排序算法。

冒泡排序实现

为了用编程语言实现冒泡排序算法，我们需要

1. 一个包含要排序值的数组。
2. 一个内部循环，它遍历数组并交换值（如果第一个值大于下一个值）。每次运行时，该循环必须遍历少一个值。
3. 一个外部循环，它控制内部循环必须运行的次数。对于包含 n 个值的数组，该外部循环必须运行 n-1 次。

生成的代码如下所示

my_array = [64, 34, 25, 12, 22, 11, 90, 5]

n = len(my_array)
for i in range(n-1):
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]

print("Sorted array:", my_array)

冒泡排序改进

冒泡排序算法可以稍微改进一下。

想象一下数组几乎已经排序好了，最小数字在开头，比如这样

my_array = [7, 3, 9, 12, 11]

在这种情况下，数组将在第一次运行后排序，但冒泡排序算法将继续运行，而不会交换元素，这是没有必要的。

如果算法遍历数组一次，没有交换任何值，那么数组必须已经排序完成，我们可以停止算法，如下所示

my_array = [7, 3, 9, 12, 11]

n = len(my_array)
for i in range(n-1):
    swapped = False
    for j in range(n-i-1):
        if my_array[j] > my_array[j+1]:
            my_array[j], my_array[j+1] = my_array[j+1], my_array[j]
            swapped = True
    if not swapped:
        break

print("Sorted array:", my_array)

冒泡排序时间复杂度

有关时间复杂度的一般解释，请访问 此页面。

有关冒泡排序时间复杂度的更详细解释，请访问 此页面。

冒泡排序算法遍历数组中的每个值，将其与相邻的值进行比较。因此，对于包含 \(n\) 个值的数组，在一个循环中必须有 \(n\) 次这样的比较。

并且在一个循环之后，数组会被再次遍历 \(n\) 次。

这意味着总共进行了 \(n \cdot n\) 次比较，因此冒泡排序的时间复杂度为

\[ \underline{\underline{O(n^2)}} \]

描述冒泡排序时间复杂度的图形如下所示

正如你所看到的，当数组的大小增加时，运行时间会快速增加。

幸运的是，还有比这更快的排序算法，比如 快速排序，我们稍后会研究。

你可以在下面模拟冒泡排序，其中红色虚线是理论时间复杂度 \(O(n^2)\)。你可以选择一个值的数量 \(n\)，并运行一个实际的冒泡排序实现，其中操作被计数，并且计数在下面的图中被标记为蓝色十字。理论与实践如何比较？

[,,,,]