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

什么是 Bubbl排序？

Bubbl电子排序 是一种排序算法，用于通过比较两个相邻值按升序对列表项进行排序。如果第一个值高于第二个值，则第一个值占据第二个值的位置，而第二个值占据第一个值的位置。如果第一个值低于第二个值，则不进行交换。

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

该 Bubbl分类 Python 教程你将学习：

实施 Bubbl排序算法

我们将把实现分为三个 (3) 步骤，即问题、解决方案和算法，我们可以使用这些步骤为任何语言编写代码。

该问题

给出一个物品列表，其顺序是随机的，我们希望将这些物品有序地排列起来

请考虑以下列表：

[21,6,9,33,3]

解决方案

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

结果应该如下：

[3,6,9,21,33]

算法

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

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

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

步骤3） 执行内层传递（n – 1）次，作为外层传递 1。获取第一个元素值并将其与第二个值进行比较。如果第二个值小于第一个值，则交换位置

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

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

步骤6） 优化算法

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

优化 Bubbl排序算法

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

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

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

优化采用以下步骤

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

步骤2） 如果值交换了位置，则继续下一次迭代

步骤3） 如果利益没有交换位置，则终止内层循环，继续外层循环。

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

视觉表现

给定一个包含五个元素的列表，下图说明了冒泡排序在对它们进行排序时如何迭代这些值

下图显示了未排序的列表

第一次迭代

步骤1）

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

21 大于 6，因此 21 占据 6 所占据的位置，而 6 占据 21 所占据的位置

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

步骤2）

将值 21 和 9 进行比较。

21 大于 9，因此我们交换 21 和 9 的位置

新名单如下

步骤3）

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

值 33 大于 21，因此不发生交换。

步骤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 产生以下结果

[6, 9, 21, 3, 33]

代码说明

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

这里，

定义一个函数bubbleSort，接受一个参数theSeq。代码不输出任何内容。
获取数组的长度并将值赋给变量 n。代码不输出任何内容
启动一个 for 循环，运行冒泡排序算法 (n – 1) 次。这是外循环。代码不输出任何内容
定义一个标志变量，用于确定是否发生交换。这是为了优化目的。代码不会输出任何内容
启动内循环，比较列表中从第一个到最后一个的所有值。代码不输出任何内容。
使用 if 语句检查左侧的值是否大于右侧的值。代码不输出任何内容。
如果条件为真，则将 theSeq[j] 的值赋给时间变量 tmp。代码不输出任何内容
将 theSeq[j + 1] 的值赋给 theSeq[j] 的位置。代码不输出任何内容
变量 tmp 的值被赋值给 theSeq[j + 1] 的位置。代码不输出任何内容
标志变量被赋值为 1，表示交换已发生。代码不输出任何内容
使用 if 语句检查变量 flag 的值是否为 0。代码不输出任何内容
如果值为 0，则我们调用 break 语句退出内层循环。
返回排序后的 theSeq 的值。代码输出排序后的列表。
定义一个包含随机数列表的变量 el。代码不输出任何内容。
将函数bubbleSort的值赋给变量result。
打印变量结果的值。

Bubble 排序优势

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

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

Bubbl缺点

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

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

复杂性分析 Bubbl电子排序

复杂性有三种类型：

1）排序复杂度

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

2）时间复杂度

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

时间复杂度可以分为：

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

3）空间复杂度

空间复杂度衡量对列表进行排序所需的额外空间量。冒泡排序仅需要一个 (1) 额外空间用于交换值的时间变量。因此，它的空间复杂度为 O (1)。

结语

冒泡排序算法的工作原理是比较两个相邻的值，如果左边的值小于右边的值，则交换它们。
实现冒泡排序算法相对简单， Python。您需要使用的只是 for 循环和 if 语句。
冒泡排序算法解决的问题是将随机项目列表转换为有序列表。
数据结构中的冒泡排序算法在列表已经排序时表现最佳，因为它执行的迭代次数最少。
当列表按相反顺序排列时，冒泡排序算法的效果不佳。
冒泡排序的时间复杂度为 O (n²）和空间复杂度为 O（1）
冒泡排序算法最适合学术目的，而不是实际应用。
优化的冒泡排序通过在检查已排序的值时跳过不必要的迭代来提高算法的效率。