冒泡排序算法（Python实现，图文并茂）

冒泡排序是一种简单的排序算法，它也是一种稳定排序算法。

冒泡排序算法的基本思想是，从序列中未排序区域的最后一个元素开始，依次比较相邻的两个元素，并将小的元素与大的交换位置。这样经过一轮排序，最后的元素被移出未排序区域，成为已排序区域的第一个元素。同样，也可以按从大到小的顺序排列。

假设待排序序列为 [5，1，4，2，8]，如果采用冒泡排序对其进行升序（由小到大）排序，则整个排序过程如下：

1) 第一轮排序，此时整个序列中的元素都位于待排序序列，依次扫描每对相邻的元素，并对顺序不正确的元素对交换位置，整个过程如下图所示：

图 1 第一轮排序

从图 1 可以看到，经过第一轮冒泡排序，从待排序序列中找出了最大数 8，并将其放到了待排序序列的尾部，并入已排序序列中。

2) 第二轮排序，此时待排序序列只包含前 4 个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如下图所示：

图 2 第二轮排序

从图 2 可以看到，经过第二轮冒泡排序，从待排序序列中找出了最大数 5，并将其放到了待排序序列的尾部，并入已排序序列中。

3) 第三轮排序，此时待排序序列包含前 3 个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如下图所示：

图 3 第三轮排序

经过第三轮冒泡排序，从待排序序列中找出了最大数 4，并将其放到了待排序序列的尾部，并入已排序序列中。

4) 第四轮排序，此时待排序序列包含前 2 个元素，对其进行冒泡排序的整个过程如下图所示：

图 4 第四轮排序

5) 当进行第五轮冒泡排序时，由于待排序序列中仅剩 1 个元素，无法再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列，如下图所示：

图 5 第五轮序列

利用冒泡排序对数列 [39，22，41，19，32，15] 进行排序。排序步骤如下：
1) 单次循环查找最大值。依次两两比较列表中元素，将最大值移到列表末尾，并打印最大值和列表的内容。

List = [39,22,41,19,32,15]　　　　　　　　　　　　       　 　#原来列表中的内容
for i in range(len(List)-1):                                  #循环
    if List[i]＞List[i + 1]:                                  #比较当前值和下一个元素
        #若前面元素较大,则交换位置,将较大的元素后移
        List[i],List[i + 1] = List[i + 1],List[i]
print('最大值为:',List[-1])                                   #打印最大值
print('依次排序后的列表为:',List)                             #打印列表

执行结果为：

最大值为:41
依次排序后的列表为:[22,39,19,32,15,41]

2) 使用两层循环实现冒泡排序：

List = [39,22,41,19,32,15]　　　　　　　　　　　        　　　#原来列表中的内容
for j in range(len(List)-1):                                  #外层for循环控制循环次数
    for i in range(len(List)-1-j):                            #内层for循环控制比较次数
        if List[i]＞List[i + 1]:                             #比较当前值和下一个元素
            List[i],List[i + 1] = List[i + 1],List[i]        #将较大的元素进行后移
print('排序后的列表为:',List)                                 #打印排序后的列表

运行程序，输出如下：

排序后的列表为:[15,19,22,32,39,41]

3) 使用函数封装冒泡排序实现的过程，并传参控制正序或倒序排列。

List = [39, 22, 41, 19, 32, 15]  # 原来列表中的内容
def bubble_sort(List, flag = True):
    for j in range(len(List) - 1):  # for 循环控制循环次数
        for i in range(len(List) - 1 - j):  # for 循环控制比较次数
            if List[i] > List[i + 1]:  # 比较当前值和下一个元素
                # 较大的元素进行后移
                List[i], List[i + 1] = List[i + 1], List[i]
    if flag:
        return List  # 如果要求正序排列直接返回排序后的结果
    else:
        return List[::-1]  # 返回反序后的列表

print('正序排列后的列表为：', bubble_sort(List, True))
print('反序排列后的列表为：', bubble_sort(List, False))

运行程序，输出如下：

正序排列后的列表为:[15,19,22,32,39,41]
反序排列后的列表为:[41,39,32,22,19,15]

冒泡排序算法（Python实现，图文并茂）

相关文章