Python算法基础：解锁冒泡排序与选择排序的奥秘

在数据处理和算法设计中，排序是一项基础且重要的操作。本文将介绍两种经典的排序算法：冒泡排序（Bubble Sort）和选择排序（Selection Sort）。我们将通过示例代码来演示这两种算法如何对列表进行升序排列。

一. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的列表，比较相邻的元素，并将顺序错误的元素进行交换。这个过程会一直进行，直到没有需要交换的元素为止。

分析

冒泡排序是一种简单的排序算法，主要思想是通过重复遍历待排序的列表，比较相邻的元素并根据顺序交换它们。每次遍历后，未排序部分的最大元素会“冒泡”到列表的末尾。因此，算法得名为“冒泡排序”。

我们先拿到需要排序的列表" [ 10, 50 , 20, 60, 40, 30] " ，我们知道冒泡排序实现的原理以后，可以自己在脑海里模拟计算机进行遍历排序：

首先，第一轮：我们先拿数列第一个数据和第二个数据比较，如果第二个数
比第一个数大，就交换两个数据的位置。然后，然后比较第二个数与第三个
数，一直到比较完整个数列，这时候，数列最小的数就已经排在最后面了，于
是后面每轮就不需要再与最后一个数据比较了。
然后后面每一轮都和第一轮一样，只不过每轮结束下一轮都可以少比较一个数据。
我们需要比较的列表是[ 10, 50, 20, 60, 40, 30]，那么我们每轮结束以后
够可以得到一个列表。
然后，让我们模拟一下，每一轮结束得到的列表应该是什么样的：
第一轮： [50, 20, 60, 40, 30, 10]
第二轮： [50, 60, 40, 30, 20, 10]
第三轮： [60, 50, 40, 30, 20, 10] # 注意，这里我们都可以看到，其实数组的排序其实已经完成了，
第四轮： [60, 50, 40, 30, 20, 10] # 但是计算机不是人类，它只会按照程序运行，继续比较。
第五轮： [60, 50, 40, 30, 20, 10]

冒泡排序的实现

以下是使用 Python 实现的冒泡排序代码，排序列表 " [10, 50, 20, 60, 40, 30] "：

# 冒泡排序 降序,升序将"<"改成">"
l0 = [10, 50, 20, 60, 40, 30]
total = 0
count = 0for i in range(len(l0) - 1):for j in range(len(l0) - i - 1):total += 1  # 统计比较次数if l0[j] < l0[j + 1]:  # 升序排序条件count += 1  # 统计交换次数temp = l0[j]  # 交换元素l0[j] = l0[j + 1]l0[j + 1] = tempprint(f"第{i + 1}轮：{l0}")print(f"比较了{total}次,数值互换了{count}次", l0)

运行结果

运行上述代码后，输出结果如下:

第一轮： [50, 20, 60, 40, 30, 10]
第二轮： [50, 60, 40, 30, 20, 10]
第三轮： [60, 50, 40, 30, 20, 10]
第四轮： [60, 50, 40, 30, 20, 10]
第五轮： [60, 50, 40, 30, 20, 10]
比较了15次,数值互换了9次 [60, 50, 40, 30, 20, 10]

在这个例子中，我们可以看到最终的排序结果是 " [10, 20, 30, 40, 50, 60] "。在排序过程中，总共进行了 15 次比较，其中 9 次进行了值的交换。

二. 选择排序

选择排序是一种不稳定的排序算法，它的基本思想是每一趟从未排序的部分中选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都排好序。这种方法的时间复杂度为 O(n^2)。

分析

选择排序是一种简单的排序算法。它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。

我们先拿到需要排序的列表" [ 10, 50 , 20, 60, 40, 30] " ，我们知道选择排序实现的原理以后，就像冒泡排序一样在脑海里模拟计算机进行遍历排序：

首先，我们定义一个循环外的变量"max_index"把它当作每轮未排序最大数值的索引第一轮：我们先把数列第一个数据当作最大值把它的索引赋予"max_index"，
然后比较l0[max_index]和第二个数据，如果第二个数比第一个数大，就把
第二个数的索引赋予max_index。然后,l0[max_index]与第三个数比较，
一直到比较完整个数列，这时候max_index就是数组最大数值的索引，交换
数列中第一个数值与最大数值的位置。然后后面每一轮都和第一轮一样，只不过每轮结束下一轮都可以少比较一个数据。
我们需要比较的列表是[ 10, 50, 20, 60, 40, 30]，那么我们每轮结束以后就
可以得到一个列表。
然后，让我们模拟一下，每一轮结束得到的列表应该是什么样的：
第1轮：[60, 50, 20, 10, 40, 30]
第2轮：[60, 50, 20, 10, 40, 30]
第3轮：[60, 50, 40, 10, 20, 30]
第4轮：[60, 50, 40, 30, 20, 10]
第5轮：[60, 50, 40, 30, 20, 10]

选择排序的实现

以下是使用 Python 实现的选择排序代码，对列表 " [60, 10, 20, 50, 40, 30] " 进行降序排序：

# 选择排序 降序, 升序将"<"改成">"
l0 = [10, 50, 20, 60, 40, 30]
total = 0
count = 0for i in range(len(l0) - 1):max_index = i  # 假设未排序部分的第一个元素为最大值for j in range(i + 1, len(l0)):total += 1  # 记录比较次数if l0[max_index] < l0[j]:  # 寻找最大值max_index = jcount += 1  # 记录交换次数# 交换当前元素和找到的最大元素temp = l0[i]l0[i] = l0[max_index]l0[max_index] = tempprint(f"第{i + 1}轮：{l0}")print(f"比较了{total}次, 数值互换了{count}次", l0)

运行结果

运行上述选择排序的代码后，输出结果如下：

第1轮：[60, 50, 20, 10, 40, 30]
第2轮：[60, 50, 20, 10, 40, 30]
第3轮：[60, 50, 40, 10, 20, 30]
第4轮：[60, 50, 40, 30, 20, 10]
第5轮：[60, 50, 40, 30, 20, 10]
比较了15次,数值互换了5次 [60, 50, 40, 30, 20, 10]

在这个例子中，最终的排序结果是 " [60, 50, 40, 30, 20, 10] "。在排序过程中，总共进行了 15 次比较，一共进行了5次值的交换。

 三. 冒泡排序与选择排序比较

性能分析

时间复杂度:

冒泡排序的时间复杂度为 O(n²)，最坏和平均情况下都是 O(n²)，最佳情况下（列表已排序）为 O(n)。

选择排序的时间复杂度也是 O(n²)，无论是最坏、平均还是最佳情况都是 O(n²)。

选择排序：

比较次数：在每一轮中，选择排序需要遍历未排序的部分以找到最大值（或最小值）。对于长度为 (n) 的列表，第一轮需要比较 (n-1) 次，第二轮需要比较 (n-2) 次，以此类推。因此，总的比较次数为：O(n^2)

交换次数：每一轮最多只进行一次交换，因此交换次数为 (O(n))。

冒泡排序：

比较次数：在每一轮中，冒泡排序需要比较相邻的元素。对于长度为 (n) 的列表，第一轮需要比较 (n-1) 次，第二轮需要比较 (n-2) 次，以此类推。总的比较次数同样为：O(n^2)

交换次数：在最坏的情况下，每一次比较都需要进行交换，因此交换次数也是 (O(n^2))。

空间复杂度:

冒泡排序是原地排序算法，空间复杂度为 O(1)。
选择排序同样是原地排序算法，空间复杂度也为 O(1)。

使用场景

冒泡排序:

1.因为其简单易懂，适合教育和教学的场景，帮助初学者理解排序的基本概念。
2.不适合处理大型数据集，效率较低。

选择排序:

1.选择排序虽然也不适合处理大型数据集，但在某些特定情况下（例如数据基本有序时），它可能会表现得比冒泡排序更好。
2.适合对小型数据集进行排序，且实现简单。

四. 总结

通过本文的介绍，我们了解了冒泡排序和选择排序这两种经典的排序算法。虽然它们在实际应用中并不常用（因为有更高效的排序算法，如快速排序和归并排序），但它们在学习算法的过程中提供了良好的基础。

代码复用在实际开发中，使用内置的排序函数会更加高效。例如，Python 提供了内置的  ' sort() ' 方法和 ' sorted() ' 函数，使用起来简单且效率高。

示例如下：

# 使用 Python 内置的排序
l0 = [10, 50, 20, 60, 40, 30]
l0.sort()  # 原地排序
print(l0)  # 输出：[10, 20, 30, 40, 50, 60]l1 = [60, 10, 20, 50, 40, 30]
sorted_l1 = sorted(l1)  # 返回新排序的列表
print(sorted_l1)  # 输出：[10, 20, 30, 40, 50, 60]

希望本文能够帮助你理解冒泡排序和选择排序的基本概念及其实现。如果你有任何问题，欢迎在评论区讨论！