Python 实现的冒泡排序
冒泡排序
Bubble Sort 是一种算法，用于将数组从最低值排序到最高值。
{{ msgDone }}
运行模拟，查看 Bubble Sort 算法对值数组进行排序时的样子。数组中的每个值都由一列表示。
'Bubble' 一词来源于此算法的工作方式，它使最高值“冒泡”。
工作原理：
- 逐个遍历数组。
- 对于每个值，将其与下一个值进行比较。
- 如果该值高于下一个值，则交换这两个值，使最高值排在最后。
- 遍历数组的次数与数组中的值数量相同。
手动运行示例
在编程语言中实现 Bubble Sort 算法之前，让我们先手动对一个短数组仅运行一次，以了解其原理。
第 1 步：从未排序数组开始。
[7, 12, 9, 11, 3]
第 2 步：查看前两个值。最低值是否排在前面？是的，因此无需交换它们。
[7, 12, 9, 11, 3]
第 3 步：向前移动一步，查看值 12 和 9。最低值是否排在前面？不是。
[7, 12, 9, 11, 3]
第 4 步：因此，我们需要交换它们，使 9 排在前面。
[7, 9, 12, 11, 3]
第 5 步：再向前移动一步，查看值 12 和 11。
[7, 9, 12, 11, 3]
第 6 步：我们必须交换它们，使 11 排在 12 前面。
[7, 9, 11, 12, 3]
第 7 步：查看值 12 和 3，我们需要交换它们吗？是的。
[7, 9, 11, 12, 3]
第 8 步：交换值 12 和 3，使 3 排在前面。
[7, 9, 11, 3, 12]
重复上述步骤，直到无需再进行交换，即可得到一个已排序数组：
在 Python 中实现冒泡排序
要在 Python 中实现 Bubble Sort 算法，我们需要：
- 待排序的数组。
- 内部循环，用于遍历数组并在第一个值高于下一个值时交换它们。每次运行时，此循环必须遍历的值数量减少一个。
- 外部循环，用于控制内部循环的运行次数。对于包含 n 个值的数组，此外部循环必须运行 n-1 次。
生成的代码如下所示：
实例
在 Python 中创建 Bubble Sort 算法：
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(n-1):
for j in range(n-i-1):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
print(mylist)
冒泡排序的改进
Bubble Sort 算法还可以进一步改进。
想象一下，如果数组已经接近排序完成，最低值位于数组开头，例如：
mylist = [7, 3, 9, 12, 11]
在这种情况下，数组在第一次运行后就会排序完成，但 Bubble Sort 算法将继续运行，而不交换任何元素，这是不必要的。
如果算法遍历数组一次而未交换任何值，则数组必定已排序完成，我们可以像这样停止算法：
实例
改进后的 Bubble Sort 算法：
mylist = [7, 3, 9, 12, 11]
n = len(mylist)
for i in range(n-1):
swapped = False
for j in range(n-i-1):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
swapped = True
if not swapped:
break
print(mylist)
冒泡排序的时间复杂度
Bubble Sort 算法遍历数组中的每个值，并将其与相邻值进行比较。因此，对于包含 \(n\) 个值的数组，一次循环中必须进行 \(n\) 次这样的比较。
然后，数组会再次被遍历 \(n\) 次。
这意味着总共需要进行 \(n \cdot n\) 次比较，因此 Bubble Sort 的时间复杂度为：\( O(n^2) \)。
描述 Bubble Sort 时间复杂度的图形如下所示：
如你所见，当数组大小增加时，运行时间会迅速增加。
幸运的是，存在比 Bubble Sort 更快的排序算法，例如快速排序，我们将在后面进行介绍。