100个python算法超详细讲解：冒泡排序

1．问题描述
对N个整数（数据由键盘输入）进行升序排列。
2．问题分析
对于N个类型相同的数，我们可利用数组进行存储。冒泡排序是利
用两个相邻元素之间进行比较交换的过程将一个无序表变成有序表。
冒泡排序的思想是：首先，从表头开始往后扫描数组，在扫描过
程中逐对比较相邻两个元素的大小。若相邻两个元素中，前面的元素
大于后面的元素，则将它们互换，称之为消去了一个逆序。在扫描过
程中，不断地将两相邻元素中的大者往后移动，最后就将数组中的最
大者换到了表的最后，这正是数组中最大元素应有的位置。然后，在
剩下的数组元素中（n-1个元素）重复上面的过程，将次小元素放到倒
数第2个位置。不断重复上述过程，直到剩下的数组元素为0为止，此
时的数组就变为了有序。假设数组元素的个数为n，在最坏的情况下需
要的比较总次数为：((n-1)+(n-2)+…+2+1)=n(n-1)/2。
3．算法设计
冒泡排序的过程我们可以用示意图简单地表示，如图1.14所示。从
整个排序过程中寻找规律，可知n个元素只需比较n-1次即可。假设一个
数组中有7个元素，现在对这7个元素进行排序，只需比较6次即可得到
所要的有序序列。示意图中最后加粗的数字即为经过一次交换位置固
定的数字。

数组名用a表示，数组下标用j表示，则数组中相邻两个元素的下标
可表示为a[j]、a[j+1]或a[j-1]、a[j]。在利用数组解决问题时需要注意数
组下标不要越界，假如定义一个整形数组int a[n]，则数组元素下标的
取值范围是0～n-1，下标小于0或者大于n-1都视为下标越界。如果相邻
元素采用a[j]、a[j+1]表示，则下标取值范围是0～n-2，如果采用a[j-
1]、a[j]表示，下标取值范围则是1～n-1，所以读者在进行编程时一定
要注数组下标越界的问题。
数组元素互换也是经常遇到的一类题型，一般这种情况下我们需
要借助一个中间变量才可以完成，对于许多初学者来说经常犯的一个
错误是对两个元素直接相互赋值，而不借助中间变量。我们先来看一
个生活中的例子，在蓝墨水瓶中装有蓝墨水，红墨水瓶中装有红墨
水，现在我们要把蓝墨水放到红墨水瓶中，红墨水放到蓝墨水瓶中。
做法是先找一个白色空瓶（作用相当于程序中的中间变量），首先将
蓝墨水倒入白色空瓶（t=a[i]或t=a[i+1]），接着将红墨水倒入蓝墨水瓶
（a[i]=a[i+1]或a[i+1]=a[i]），最后将白瓶中的蓝墨水倒入红墨水瓶
（a[i+1]=t或a[i]=t），经过这三步就完成了红墨水与蓝墨水的互换。如
果不借助白色空瓶，直接把蓝墨水倒入红墨水瓶或把红墨水倒入蓝墨
水瓶，这样必将破坏原来所存储的内容。
第一次的交换过程可以用简单的程序段进行表示，代码如下：

for j in range(0, n-1):
if a[j] > a[j+1]:
t = a[j] # 使用变量t暂存
a[j] = a[j+1]
a[j+1] = t

 第二次的交换过程（最后一个元素经过第一轮比较已经确定，不
需要再次进行比较）可表示为：

for j in range(0, n-2):
if a[j] > a[j+1]:
t = a[j] # 使用变量t暂存
a[j] = a[j + 1]
a[j + 1] = t

第三次的交换过程（最后两个元素已经确定，不需要再次进行比
较）可表示为：

for j in range(0, n-3):
if a[j] > a[j+1]:
t = a[j] # 使用变量t暂存
a[j] = a[j + 1]
a[j + 1] = t

由上面的程序段可以发现，第一次比较的判定条件为j 次为j i。在编程过程中我们可以用两层循环来控制，第一层循环控制交换的
轮数，第二层循环控制每轮需要交换的次数。
4．完整的程序
程序流程图如图1.15所示。

根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 冒泡排序
def bubbleSort(a):
# 首先获取列表list的总长度，为之后循环比较做准备
n = len(a)
# 进行 n-1 次比较，控制比较的轮数
i = 1
while i <= n-1:
# 控制每轮比较的次数
j = 0
while j < n-i:
# 交换
if a[j] > a[j+1]:
t = a[j]
a[j] = a[j+1]
a[j+1] = t
j += 1
i += 1
# 打印每一轮交换后的列表
for a1 in a:
print(a1, end=" ")
if __name__=="__main__":
print("请为列表元素赋初值，列表末尾不能有空格：")
x = input()
a = x.split(" ") # 以空格方式分割每个元素
for i in range(0, len(a)): # 输入多个值
a[i] = int(a[i])
print("你输入的列表元素为：\n", a)
print("经过交换后的数组元素为：")
bubbleSort(a)

 5．运行结果
在PyCharm下运行程序，屏幕上提示“请为数组元素赋初值，列表
末尾不能有空格：”，输入两组不同的初值，运行结果如图1.16所示。

6．问题拓展
常用的排序方法除了上述的冒泡法外，还有选择排序、插入排
序、快速排序、堆排序等，下面简单介绍选择排序。
选择排序的思想是：扫描整个线性表，第一轮比较拿数组中的第
一个元素与其他元素进行比较，遇到比第一个元素小的元素则进行交
换，再拿着交换之后的第一个元素接着从上次比较的位置与后面的元
素进行比较，直到扫描到线性表的最后，从中选出最小的元素，将它
交换到表的最前面（这是它应有的位置）；第二轮比较的时候从第二
个元素开始，依次与第三个、第四个直到最后一个进行比较，在比较
过程中有比第二个元素小的元素则进行交换，接着与后面的元素比
较；对剩下的子表采用同样的方法，直到子表为空。在最坏的情况
下，需要比较n(n-1)／2次。

完整的程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 选择排序
def selectionSort(a):
# 求出列表的长度
n = len(a)
for i in range(0, n-1):
for j in range(i+1, n):
#交换
if a[j] < a[i]:
t = a[i]
a[i] = a[j]
a[j] = t
for i in a:
print(i, end=" ")
if __name__=="__main__":
print("请为列表元素赋初值，列表末尾不能有空格：")
x = input()
a = x.split(" ") # 以空格方式分割每个元素
for i in range(0, len(a)): # 输入多个值
a[i] = int(a[i])
print("你输入的列表元素为：\n", a)
print("经过交换后的数组元素为：")
selectionSort(a)

 不同排序法的效率是不同的，不同需求情况下可选择不同的方
法。其他几种排序方法的原理有兴趣的读者可参阅数据结构的相关内
容。