2.8 实战
2.8.1 二分查找
1．顺序查找
若要查找一个序列中是否存在某个元素，一般可以采用遍历的方法查找。例如：
arr=[12,46,25,43,58,7,37,5,80,34,105,82] v=int（input（"输入你要查找的数"）） ok=False for e in arr: if e==v: ok=True break if ok: print（’查找成功！'） else: print（’查找失败！'）
执行：
输入你要查找的数6 查找成功！
分析这个程序的时间效率。如果一个序列中数据元素的个数为n，且每个元素被查找的概率是均等的（1/n），在查找成功的情况下，第1、2、3、…、n元素的比较次数分别为1、2、3、…、n，因此，查找成功的情况下查找一个元素的平均比较次数是1（1/n）+2（1/n）+...+n（1/n）=（n+1）/2，即平均需要比较的次数是表长的一半。当n趋向于无穷大时，（n+1）/2和n在一个数量级，所以称其时间复杂度是O（n），即查找时间和n是同阶无穷大量。
假如n=1024，则成功查找其中的一个元素需要平均比较512次。但如果这个序列是有序的，那么可以使用“二分查找”的算法，平均只需要log2（1024）次，即10次就可以找到该元素。
2．二分查找
“二分查找”的思想很简单。例如，在一个有序序列alist中查找某个元素item，则可以让item首先和alist的中间元素比较：
● 如果相等，则成功；
● 如果小于中间元素，则在alist的左半区间查找；
● 如果大于等于中间元素，则在alist的右边半区间查找。
如图2-3所示，是在一个有序序列中查找25的过程。
图2-3 查找25的过程
以上查找过程是利用一个循环迭代过程，通过不断更新区间的左右位置L、H和中间位置Middle这3个指示器来查找。程序如下：
def binarySearch（alist, value）: L=0 #区间左端点 H=len（alist）-1 #区间右端点 found=False while L<=H: #区间（L, H）存在 Middle=（L+H）//2 #Middle指向区间的中点 if alist[Middle]==value: #等于Middle指向的元素，找到了 return Middle else: if value < alist[Middle]: H=Middle-1 #在左区间查找 else: L=Middle+1 #在右区间查找 return -1 testlist=[5,7,12,25,34,37,43,46,58,80,82,105] print（binarySearch（testlist, 25）） print（binarySearch（testlist, 13））
输出：
3 -1
2.8.2 冒泡排序和简单选择排序
1．冒泡排序
冒泡排序的思想是对相邻元素比较大小，如果逆序就交换它们。冒泡排序如图2-4所示，对于一个序列，通过这种两两相邻元素的比较与交换，可以将最大值（或最小值）放在最后一个位置，这一过程称为“一趟冒泡”。“一趟冒泡”只是在一个序列中选出了一个最大值（或最小值）并放在了其最终位置。对于剩余元素构成的序列，再进行“一趟冒泡”，又可以在剩余元素序列中选出一个最大值（或最小值）并放在剩余元素序列的最终位置（如倒数第二个位置）。重复这个过程，直到剩余一个元素位置。对于n个元素的序列，需要进行n-1趟冒泡。程序如下：
图2-4 冒泡排序
alist=[49,38,27,97,76,13,27,49] debug=True for i in range（len（alist）-1,0, -1）: for j in range（i）: if alist[j]>alist[j+1]: #temp=alist[j] #alist[j]=alist[j+1] #alist[j+1]=temp alist[j], alist[j+1]=alist[j+1], alist[j] #交换两个元素 if debug: print（alist） print（alist）
输出：
[38, 27, 49, 76, 13, 27, 49, 97] [27, 38, 49, 13, 27, 49, 76, 97] [27, 38, 13, 27, 49, 49, 76, 97] [27, 13, 27, 38, 49, 49, 76, 97] [13, 27, 27, 38, 49, 49, 76, 97] [13, 27, 27, 38, 49, 49, 76, 97] [13, 27, 27, 38, 49, 49, 76, 97] [13, 27, 27, 38, 49, 49, 76, 97]
2．简单选择排序
简单选择排序的思想是：在整个序列中选出一个最值（如最小值）放在序列的开头（或结束）位置。这个过程称为“一趟选择”。对于剩余元素构成的序列重复这个过程，又选出一个最值放在剩余元素序列的开头（或结束）位置，即“第二趟选择”。这个过程一直进行下去，直到剩余序列只有一个元素。请读者根据这个思想写出简单选择排序的程序。
2.8.3 Floyd最短路径算法
1．最短（最佳）路径问题
最短路径问题是日常生活和科学研究中广泛应用的问题。例如，一个人在一个陌生城市，要从某一个地点前往另外一个地点，此时他会打开手机中的导航软件，导航软件会按照不同代价（时间、路程、花费）给出不同的最佳（最短）路径。再如，计算机网络通信需要在不同计算机之间发送数据包，网络路由算法会采用最短路径算法计算出最佳的数据包发送路径。
如图2-5（a）所示的一个城市公路图。其中，顶点表示城市，而边表示城市之间的公路及其距离，现在要求出任何两个城市之间的最短路径。最短路径属于图论的一个基本问题，针对这个问题有很多最短路径算法，其中的Floyd算法可以求出任意两个顶点之间的最短路径。
图2-5 城市公路图及其邻接矩阵
2.Floyd算法
Floyd算法的基本思想是：用一个二维矩阵（如图2-5（b）所示）表示任意两个顶点之间的距离，初始时，这个矩阵的数据元素的值表示的是两个城市的直达距离，值是无穷大∞则表示没有直达距离。
直达距离不一定是最短距离（顶点0到顶点2的直达距离6不是顶点0到顶点2的最短距离），因此，Floyd算法每次考虑绕道一个顶点，查看是否有两个顶点的距离会因为绕道这个顶点变得更近。
假如当前的距离矩阵为D，现在绕道顶点w，查看顶点u到顶点v之间的距离D[u][v]会不会因为绕道顶点w变得更短。如果更短，则更新D[u][v]=D[u][w]+ D[w][v]，即：
if D[u][w]+ D[w][v] < D[u][v]:
D[u][v]= D[u][w]+ D[w][v]
对这个绕道顶点w，检查所有其他的顶点u、v是否因为绕道w而变得更短，从而更新距离矩阵D。
不断重复绕道不同的顶点，并更新这个距离矩阵D，直到所有顶点都绕道完为止，得到的最终矩阵就是这两个顶点的最短距离。
为了记录路径，需要用一个和D一样大小的二维矩阵P记录任意两个顶点之间的当前距离对应的路径上的倒数第二个顶点（路径上终点之前的那个顶点）。例如：
if D[u][w]+ D[w][v] < D[u][v] :
D[u][v]= D[u][w]+ D[w][v]
P[u][v]= P[w][v] #P[u][v]= P[u][w]+ P[w][v]
下面是Floyd算法的Python代码实现：
n=4 INFINITY=100000.0 #假设这是一个很大的数值 D=[[0,2,6,4], #距离矩阵 [INFINITY,0,3, INFINITY], [7, INFINITY,0,1], [5, INFINITY,12,0]] P=[[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]] #路径矩阵 //初始化路径矩阵，即P[u][v]记录直达路径uv的终点v前面的顶点u for u in range（0, n）: for v in range（0, n）: P[u][v]=u print（＊D, sep="\n"） #＊D是"解封参数列表"传递参数方式 #sep="\n"表示每个输出元素之间的分割符是换行符"\n" print（） print（＊P, sep="\n"） print（） for w in range（0, n）: #绕道顶点w for u in range（0, n）: for v in range（0, n）: #其他顶点u、v会不会因为绕道w距离变得更短呢？ if w!=u and w!=v and D[u][w] + D[w][v] < D[u][v] : D[u][v]=D[u][w] + D[w][v] P[u][v]=P[w][v] print（＊D, sep="\n"） print（） print（＊P, sep="\n"）
输出结果：
[0, 2, 6, 4] [100000.0, 0, 3, 100000.0] [7, 100000.0, 0, 1] [5, 100000.0, 12, 0] [0, 0, 0, 0] [1, 1, 1, 1] [2, 2, 2, 2] [3, 3, 3, 3] [0, 2, 5, 4] [9, 0, 3, 4] [6, 8, 0, 1] [5, 7, 10, 0] [0, 0, 1, 0] [3, 1, 1, 2] [3, 0, 2, 2] [3, 0, 1, 3]
根据路径矩阵P，对于任何一对顶点u、顶点v，其路径可以从终点倒过来追踪到起点，即终点是v，其前一个顶点是P[u][v]，再前一个顶点是P[u][ P[u][v] ]、...
for u in range（0, n）: for v in range（0, n）: if u==v continue print（u, ’到’, v, ’的逆向路径是：', end=' '） print（v, end=', '） w=P[u][v] while w!=u: print（w, end=', '） w=P[u][w] print（u）
输出结果：
0到1的逆向路径是：1,0 0到2的逆向路径是：2,1,0 0到3的逆向路径是：3,0 1到0的逆向路径是：0,3,2,1 1到2的逆向路径是：2,1 1到3的逆向路径是：3,2,1 2到0的逆向路径是：0,3,2 2到1的逆向路径是：1,0,3,2 2到3的逆向路径是：3,2 3到0的逆向路径是：0,3 3到1的逆向路径是：1,0,3 3到2的逆向路径是：2,1,0,3