下载掌阅APP，畅读海量书库
立即打开
冒泡排序是一种简单的排序算法，它也是一种稳定排序算法。冒泡排序算法的基本思想：从序列中未排序区域的最后一个元素开始，依次比较相邻的两个元素，并将小的元素与大的交换位置。这样经过一轮排序，最后的元素被移出未排序区域，成为已排序区域的第一个元素。同样，也可以按从大到小的顺序排列。
假设待排序序列为[5，1，4，2，8]，如果采用冒泡排序对其进行升序（由小到大）排序，则整个排序过程如下：
（1）第一轮排序，此时整个序列中的元素都位于待排序序列，依次扫描每对相邻的元素，并对顺序不正确的元素对交换位置，整个过程如图3-2所示。
图3-2 第一轮排序
从图3-2可以看到，经过第一轮冒泡排序，从待排序序列中找出了最大数8，并将其放到了待排序序列的尾部，并入已排序序列中。
（2）第二轮排序，此时待排序序列只包含前4个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如图3-3所示。
图3-3 第二轮排序
从图3-3可以看到，经过第二轮冒泡排序，从待排序序列中找出了最大数5，并将其放到了待排序序列的尾部，并入已排序序列中。
（3）第三轮排序，此时待排序序列包含前3个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如图3-4所示。
图3-4 第三轮排序
经过第三轮冒泡排序，从待排序序列中找出了最大数4，并将其放到了待排序序列的尾部，并入已排序序列中。
（4）第四轮排序，此时待排序序列包含前2个元素，对其进行冒泡排序的整个过程如图3-5所示。
图3-5 第四轮排序
（5）当进行第五轮冒泡排序时，由于待排序序列中仅剩1个元素，无法再进行相邻元素的比较，因此直接将其并入已排序序列中，此时的序列就认定为已排序好的序列，如图3-6所示。
图3-6 第五轮序列
【例3-7】 利用冒泡排序对数列[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）使用函数封装冒泡排序实现的过程，并传参控制正序或倒序排列。
运行程序，输出如下：
正序排列后的列表为：[15,19,22,32,39,41]
反序排列后的列表为：[41,39,32,22,19,15]