Bubbl排序算法 Python 使用列表示例

什么是 Bubbl排序？

Bubbl电子排序 是一种排序算法，它通过比较两个相邻的值来对列表项进行升序排序。如果第一个值大于第二个值，则第一个值移到第二个值的位置，第二个值移到第一个值的位置。如果第一个值小于第二个值，则不进行交换。ping 已经完成了。

重复此过程，直到列表中的所有值都已比较并交换（如有必要）。每次迭代通常称为一次传递。冒泡排序中的传递次数等于列表中元素的数量减一。

在本 Bubbl分类 Python 教程 您将了解它所解决的问题、其优化形式、分步可视化演示以及工作原理。 Python 程序及其性能特点。

实施 Bubbl排序算法

我们将把实现过程分解为三个（3）步骤，即问题、解决方案和我们可以用来为任何语言编写代码的算法。

该问题

给定一个随机排列的物品清单，我们希望将这些物品按顺序排列。

请考虑以下列表：

[21, 6, 9, 33, 3]

解决方案

遍历列表，比较两个相邻元素并交换它们。ping 如果第一个值高于第二个值，则它们相等。

结果应该如下：

[3, 6, 9, 21, 33]

算法

冒泡排序算法的工作原理如下：

步骤1） 获取元素总数。获取给定列表中的项目总数。

步骤2） 确定需要执行的外层传递次数（n – 1）。其长度为列表减一。

步骤3） 对外部遍历 1 执行 (n – 1) 次内部遍历。获取第一个元素的值并将其与第二个值进行比较。如果第二个值小于第一个值，则交换它们的位置。

步骤4） 重复步骤 3 的操作，直到到达最外层（n – 1）。获取列表中的下一个元素，然后重复步骤 3 中执行的过程，直到所有值都按正确的升序排列。

步骤5） 所有遍历完成后返回结果。返回排序后的列表。

步骤6） 优化算法。

如果列表或相邻值已排序，则避免不必要的内部传递。例如，如果提供的列表已包含按升序排序的元素，那么我们可以提前中断循环。

优化 Bubbl排序算法

默认情况下，冒泡排序的算法 Python 比较列表中的所有项目，无论列表是否已排序。如果给定的列表已经排序，则比较所有值会浪费时间和资源。

优化冒泡排序可以帮助我们避免不必要的迭代，节省时间和资源。

例如，如果第一项和第二项已经排序，则无需迭代其余值。迭代终止，并启动下一个迭代，直到过程完成，如下所示 Bubble 排序示例。

优化过程按以下步骤进行：

步骤1） 创建一个标志变量，用于监控是否有任何交换ping 发生在内循环中。

步骤2） 如果数值位置互换，则继续进行下一次迭代。

步骤3） 如果这些值没有交换位置，则终止内层循环，并继续执行外层循环。

优化的冒泡排序更有效率，因为它只执行必要的步骤并跳过不需要的步骤。

视觉表现

给定一个包含五个元素的列表，下图说明了冒泡排序在排序时如何遍历这些值。

下图显示的是未排序的列表：

第一次迭代

步骤1）

比较值 21 和 6，检查哪一个大于另一个。

21 大于 6，所以 21 占据 6 的位置，而 6 占据 21 的位置。

我们修改后的列表现在看起来像上面的列表。

步骤2）

将值 21 和 9 进行比较。

21 大于 9，所以我们交换 21 和 9 的位置。

新名单如上所示。

步骤3）

比较值 21 和 33，以找出较大者。

数值 33 大于 21，因此无需交换。ping 发生。

步骤4）

比较值 33 和 3，以找出较大者。

值 33 大于 3，因此我们交换它们的位置。

第一次迭代结束后的排序列表与上面的列表类似。

第二次迭代

第二次迭代后的新列表如下：

第三次迭代

第三次迭代后的新列表如下：

第四次迭代

第四次迭代后的新列表如下：

Python 例子

下面的代码展示了如何实现 Bubbl排序算法 Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

在以下代码中执行上述冒泡排序程序 Python 产生以下结果：

[3, 6, 9, 21, 33]

Code 说明

对于 Python Bubble排序程序代码如下：

这里，

1. 定义一个函数bubbleSort，接受一个参数theSeq。代码不输出任何内容。
2. 获取数组的长度并将该值赋给变量 n。该代码不输出任何内容。
3. 启动一个 for 循环，该循环会执行冒泡排序算法 (n – 1) 次。这是外层循环。代码不会输出任何内容。
4. 定义一个标志变量，用于判断是否发生了交换操作。这样做是为了优化性能。代码本身不会输出任何内容。
5. 启动内循环，比较列表中从第一个到最后一个的所有值。代码不输出任何内容。
6. 使用 if 语句检查左侧的值是否大于右侧的值。代码不输出任何内容。
7. 如果条件为真，则将 theSeq[j] 的值赋给一个临时变量 tmp。该代码不输出任何内容。
8. 将 theSeq[j + 1] 的值赋给 theSeq[j] 的位置。这段代码没有输出任何内容。
9. 变量 tmp 的值被赋给 theSeq[j + 1] 处。这段代码没有输出任何内容。
10. 标志变量被赋值为 1，表示发生了交换操作。代码不会输出任何内容。
11. 使用 if 语句检查变量 flag 的值是否为 0。该代码不输出任何内容。
12. 如果值为 0，则我们调用 break 语句退出内层循环。
13. 返回排序后的 theSeq 的值。代码输出排序后的列表。
14. 定义一个包含随机数列表的变量 el。代码不输出任何内容。
15. 将函数bubbleSort的值赋给变量result。
16. 打印变量结果的值。

Bubble 排序优势

以下是冒泡排序算法的一些优点：

• 很容易理解。
• 当列表已经排序或几乎排序完毕时，它的表现非常出色。
• 它不需要大量内存。
• 编写该算法的代码很容易。
• 与其他排序算法相比，其空间要求极小。

Bubbl缺点

以下是冒泡排序算法的一些缺点：

• 对大型列表进行排序时，它的性能不佳。它耗费太多时间和资源。
• 它主要用于学术目的，而不是实际应用。
• 对列表进行排序所需的步骤数为 n².

复杂性分析 Bubbl电子排序

复杂性分为三种类型：

1）排序复杂度

排序复杂度用于表示对列表进行排序所需的执行时间和空间。冒泡排序需要 (n – 1) 次迭代才能对列表进行排序，其中 n 是列表中元素的总数。

2）时间复杂度

冒泡排序的时间复杂度为O(n²).

时间复杂度可以分为：

• 最糟糕的情况 – 这是提供的列表按降序排列的地方。该算法执行的最大执行次数表示为 [Big-O] O(n²).
• 最好的情况 – 当提供的列表已经排序时，就会发生这种情况。该算法执行最少的执行次数，表示为 [大Ω] Ω(n)。
• 平均情况 – 当列表顺序随机时，就会发生这种情况。平均复杂度表示为 [Big-theta] ⊝(n²).

3）空间复杂度

空间复杂度衡量的是排序列表所需的额外空间量。冒泡排序只需要一个（1）额外空间来存储用于交换的时间变量。ping 因此，它的空间复杂度为 O(1)。

常见问题