程序设计导论：Python语言实践

4.2.2　插入排序算法

二分查找算法要求数组必须是排好序的，排序还有许多其他直接的应用，所以我们接下来讨论排序算法。首先我们讨论暴力算法，然后讨论可以用于大型数组的复杂算法。

我们讨论的暴力算法称为插入排序算法（insertion sort）。算法基于人们用来排列一手扑克牌的基本方法，即每次处理一张扑克牌，然后把它插入到已经处理好的扑克牌中，使它们保持按序排列。

程序4.2.3　二分查找法（在一个排序数组中，binarysearch.py）

程序4.2.3中的search()方法使用二分查找算法查找一个关键字位于排序数组中的索引下标（如果在数组中不存在该关键字，则返回-1）。测试客户端是一个异常过滤器，从一个命令行参数指定的白名单列表文件中读取一个排序字符串数组，然后输出来自标准输入的不包含在白名单中的单词。程序4.2.3的运行过程和结果如下：

程序4.2.4（insertion.py）包含了sort()函数的一种实现，模拟了上述过程，用于对长度为n的数组a[]中的元素进行排序。测试客户端从标准输入读取所有字符串，并把它们放置到一个数组中，然后调用sort()函数进行排序，最后把排好序的结果写入标准输出。

在insertion.sort()中，外层for循环对数组的前i个元素进行排序。内层while通过把a[i]插入到数组的适当位置完成排序，图4-2-5显示了i为6时插入排序的执行情形： ...