3.4　结构化程序示例

本节将结合结构化程序设计的思路，讲解使用Python实现冒泡排序。冒泡排序将用到前面讲解的条件判断语句和循环语句等知识。冒泡排序是数据结构中的一种排序算法，学过数据结构课程的读者应该不陌生。

冒泡排序的基本思想是，将需要排序的元素看作一个个“气泡”，最小的“气泡”最快浮出水面，排在前面。较小的“气泡”排在第二个位置，以此类推。冒泡排序需要对数列循环若干次，例如数列中有i个元素。第一遍循环，自底向上检查一遍这个数列，比较相邻的两个元素。如果较小的元素在数列的下面，把较小的元素排在前面。依次比较之后，就把最大的元素置于底部了，第二遍循环就不需要比较最后一个元素了。以此类推，第n遍循环只需要从第一个元素开始，比较i-n次。经过i-1遍处理后，数列就排序完成了。

假设有一个数列[23，12，9，15，6]，这个数列的排序过程如图3-2所示。

图3-2　冒泡排序程序的模块分解

冒泡排序的程序可以分解为两个模块，冒泡算法的实现函数和主函数，如图3-3所示。

图3-3　冒泡排序程序的模块分解

下面【例3-9】中的这段代码实现了冒泡排序。

【例3-9.py】

---

01     # 冒泡排序
02     def bubbleSort(numbers):                             # 冒泡算法的实现
03         for j in range(1,len(numbers)):                    # 循环语句负责设置冒泡排序进行的次数
04             for i in range(len(numbers)-j):             # i为列表的下标
05                 if numbers[i] > numbers[i+1]:            # 把数值小的数字放到顶端
06                     numbers[i], numbers[i+1] = numbers[i+1], numbers[i]  
07                 print (numbers)
08     
09     def main():                                               # 主函数
10         numbers = [23, 12, 9, 15, 6]                     # 定义numbers列表
11         bubbleSort(numbers)                                   # 调用bubbleSort函数
12     
13     if __name__ == '__main__':
14         main()

---

【代码说明】

·第2行代码定义bubbleSort()函数以实现冒泡排序。

·第3行代码确定每遍循环的比较次数。

·第4行代码循环比较相邻的两个元素。

·第5行代码判断相邻两个元素的大小。

·第6行代码把数值较小的数排到前面。

·第7行代码输出每遍循环的比较结果。输出结果：

---

[12, 23, 9, 15, 6]
[12, 9, 23, 15, 6]
[12, 9, 15, 23, 6]
[12, 9, 15, 6, 23]
[9, 12, 15, 6, 23]
[9, 12, 6, 15, 23]
[9, 6, 12, 15, 23]
[6, 9, 12, 15, 23]

---