第14章 算法-浙江高中信息技术知识点

浙江高中技术培优算法（陶小波） 64 第十四章 算法 1. 算法效率，同一个问题会有可能有不同的解决办法，也就是说可能有不 同的算法，就如同“一题多解”一样。有的算法效率高一些，有的算法效率低一 些。通常，算法效率的高低可由算法复杂度来度量。算法复杂度又分为时间复杂 度和空间复杂度，时间复杂度反映算法执行所需要的时间，空间复杂度反映算法 复杂度所需要占用的存储空间，每个算法的复杂度都不是固定的。 2. 常见的时间复杂度的耗时比较：O(1)<=O(log2n)<=O(n)<=O(n²) 如下图 所示 常见算法复杂度 算法名 复杂度 解析 O(1) 枚举、递归 O(n) 冒泡排序、选择排序 O(n²) 对分查找法 O(log2n) （一）递归 递归需要满足两个条件 1.确定递归公式、2.递归结束条件 递归通过对递归工作栈的压栈和出栈操作实现计算 例如：求 5！ def f(x): If x==1: #结束条件 return 1 else: return f(x-1)*x #递归公式 计算过程： f(5)=f(4)*5 递归工作栈中入栈*5 f(4)=f(3)*4 递归工作栈中入栈*4 f(3)=f(2)*3 递归工作栈中入栈*3 f(2)=f(1)*2 递归工作栈中入栈*2 f(1)=1 递归工作栈中入栈 1 根据栈的原理，出栈顺序为 1、*2、*3、 *4 和*5，最后计算得 120 【仅供参考】 （二）排序 考纲中的排序包括冒泡排序，选择排序。但是在实际解题中还会碰到其他排序， 例如桶排序、插入排序、选择排序、索引排序及冒泡排序的优化。本文将针对冒 泡、选择、插入、选择排序、桶排序、索引排序及冒泡排序优化进行分析。 升序排：从小到大排序，降序排：从大到小排序 浙江高中技术培优算法（陶小波） 65 (1) 冒泡排序 冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是 通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位 置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序比较 次数(n*(n-1))/2 有如下公共代码： import random ls=[] n=5 for i in range(n): ls.append(random.randint(10,100)) for i in range(n-1): for j in range(n-1,i,-1): if ls[j]>ls[j-1]: ls[j],ls[j-1]=ls[j-1],ls[j] 降序排(从后往前冒泡） for i in range(n-1): for j in range(n-1,i,-1): if ls[j]<ls[j-1]: ls[j],ls[j-1]=ls[j-1],ls[j] 升序排(从后往前冒泡） for i in range(n-1): for j in range(0,n-i-1): if ls[j]>ls[j+1]: ls[j],ls[j+1]=ls[j+1],ls[j] 升序排(从前往后冒泡） for i in range(n-1): for j in range(1,n-i): if ls[j]>ls[j-1]: ls[j],ls[j-1]=ls[j-1],ls[j] 降序排(从前往后冒泡） for i in range(n-1): flag=False for j in range(n-1,i,-1): if ls[j]>ls[j-1]: ls[j],ls[j-1]=ls[j-1],ls[j] Flag=True If flag==False： break 冒泡优化 1 k = n - 1 last = 0 for i in range(n - 1): flag = True for j in range(k): if ls[j] > ls[j + 1]: ls[j],ls[j+1]=ls[j+1],ls[j] last = j flag = False k = last if flag: break 冒泡优化 2 浙江高中技术培优算法（陶小波） 66 (2) 选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在 剩余元素里面给第二个元素选择第二小的，依次类推，直到第 n-1 个元素，第 n 个元素不用选择了。 有如下公共代码： import random ls=[] n=5 for i in range(n): ls.append(random.randint(10,100)) (3) 桶排序 桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数 组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法 或是以递归方式继续使用桶排序进行排序）。。 n=10 ls=[random.randint(1,100) for i in range(n)]#生成随机数 bucket=[0]*101 #新建一个范围在[0,100]之间的桶 for i in ls:#入桶 bucket[i]+=1 for i in range(1,100):#出桶 for j in range(bucket[i]): print(i,end=",") for i in range(n-1): k=i for j in range(i+1,n): if ls[j]<ls[k]: k=j if k!=i: ls[k],ls[i]=ls[i],ls[k] 选择排序写法 1 for i in range(n-1): for j in range(i+1,n): if ls[i]>ls[j]: ls[i],ls[j]=ls[j],ls[i] 选择排序写法 2 浙江高中技术培优算法（陶小波） 67 (4) 插入排序 插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效 的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入 到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过 程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当 前元素前面有序表进行待插入位置查找，并进行移动 import random j = 0 n = 5 a=[random.randint(1,100) for i in range(n)]#生成随机数 for i in range(0,n): key = a[i] j = i - 1 while j >= 0 and key < a[j]: a[j+1] = a[j] j = j - 1 a[j+1]= key (5) 插入排序(写法 2） import random n = 5 a=[random.randint(1,100) for i in range(n)]#生成随机数 for i in range(n): key = a[i] for j in range(i-1,-2,-1): if key >= a[j]: break else: a[j + 1] = a[j] a[j + 1] = key print(a) 浙江高中技术培优算法（陶小波） 68 (6) 索引排序 索引排序，是基于冒泡排序法的一种优化算法，算法核心是:用一个数组元素的 值 做 另 一 个 数 组 元 素 的 下 标 ， 然 后 交 换 下 标 。 例 如 a[b[1]]<a[b[2]] :t=b[1]:b[1]=b[2]:b[2]=t。代码如下： import random n=10 ls=[random.randint(1,100) for i in range(n)]#生成随机数 xb=[i for i in range(n)] for i in range(n-1): for j in range(n-1,i,-1): if ls[xb[j]]>ls[xb[j-1]]: xb[j],xb[j-1]=xb[j-1],xb[j] for i in range(n): print(ls[xb[i]]) (7) 易考点 a相同根据 b排序 ls=[['A',2,0],['C',1,1],['F',3,1],['C',0,1]] for i in range(len(ls)-1): for j in range(len(ls)-1,i,-1): if ls[j][1]>ls[j-1][1] or (ls[j][1]==ls[j-1][1] and ls[j][2]<ls[j-1][2]): ls[j],ls[j-1]=ls[j-1],ls[j] #二维数组要整个交换 print(ls) 排序数组中的其中一段 #flag=-1 降序，flag=1 升序 def sorts(ls,st,ed,flag): for i in range(st,ed): for j in range(ed,i,-1): if ls[j]*flag>ls[j-1]*flag: ls[j],ls[j-1]=ls[j-1],ls[j] return ls ls=[1,3,2,4,5,7,9,8,0,6] print(sorts(ls,0,9,-1)) 浙江高中技术培优算法（陶小波） 69 (8) 计数排序（求最值） import random n = 5 a=[random.randint(1,100) for i in range(n)]#生成随机数[82, 43, 60, 27, 30] ls=[0]*n for i in range(n): for j in range(n): if a[i]<a[j]: ls[i]+=1 print(a) so=[] k=0 while len(so)!=len(a): if ls[k] == max(ls): so.append(a[k]) ls[k]=-1 k=(k+1)%len(a) print(so)#排序后的结果 for i in range(len(ls)): if ls[i]==len(ls)-1: print("最小值是",a[i]) if ls[i] == 0: print("最大值是", a[i]) 浙江高中技术培优算法（陶小波） 70 (9) 快速排序（递归版本） def partition(arr, low, high): i = (low - 1) pivot = arr[high] for j in range(low, high): if arr[j] <= pivot: i = i + 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 def quickSort(arr, low, high): if low < high: pi = partition(arr, low, high) quickSort(arr, low, pi - 1) quickSort(arr, pi + 1, high) arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr, 0, n - 1) print("排序后的数组:") for i in range(n): print(arr[i]) 浙江高中技术培优算法（陶小波） 71 （三）查找算法 (1) 顺序查找最后一个 对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直 到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。 例如有 20 个数 最优的情况是第一个就找到了 即查找一次 最坏的情况 最后一 个才找到 即找了 20 次 ，下面代码就是标准的顺序查找算法功能是找到的是最 后一个等于 Key 的位置，并用变量 k记录。用 flag 表示是否查找到过该数 import random n=20 #待查找的数的总数 key=random.randint(1,50) #生成待查找的数 key ls=[random.randint(1,50) for i in range(n)] flag=False#是否查找到 key‘’ k=-1 #记录位置 for i in range(len(ls)): if ls[i]==key: flag=True k=i if flag: print("查找到 key 的位置在",k) else: print("查无此数") (2) 顺序查找第一个 在顺序查找中，还有一个比较特殊的存在，即查找第一个，例如有列表[1,2,2,2] 需要通过顺序查找法，查找到第一个 2,那么就需要在代码中控制，当第一次出 现 2时，就立马 break 出当前循环，代码如下 import random n=20 #待查找的数的总数 key=random.randint(1,50) #生成待查找的数 key ls=[random.randint(1,50) for i in range(n)] flag=False#是否查找到 key for i in range(len(ls)): if ls[i]==key: flag=True break if flag: print("查找到 key 的位置在",i) else: print("查无此数") 浙江高中技术培优算法（陶小波） 72 对分查找 对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位 置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数 组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法 进行查找，直到获得最终结果。 对分查找有如下性质： 1. 对分查找法要求待查找的数组值是有序等。 2. 对分查找法最多比较次数为 ���2(�) + 1 3. 对分查找法平均比较次数为 (1) 标准对分代码写法 import random n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=33 #待查找的数(例如查找 33) i,j,m,flag=0,n-1,0,False #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j and flag==False: m=(i+j)//2 if ls[m]==key: flag=True break elif ls[m]>key: j=m-1 else: i=m+1 if flag: print("查找到该值，位置为",m) else: print("查无此数") 浙江高中技术培优算法（陶小波） 73 例如：有数组长度为 10 的列表 其中值分别为 21, 25, 26, 29, 31, 33, 35, 37, 38, 39 通过对分查找算法查找 33，对应的 i,j,m,flag 的变化如表 1所示 初值 第一次 第二次 第三次 m=0 m=4 m=7 m=5 i=0 i=5 i=5 i=5 j=9 j=9 j=6 j=6 flag=false flag=false flag=false flag=true:循环 退出 表 1 当然，对分查找法与数据结构中的二叉树思想一致，所以我们也可以用二叉树来 表示对分查找算法的对分过程。如下图 浙江高中技术培优算法（陶小波） 74 (2) 标准对分查找变式 import random n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=33 #待查找的数 i,j,m=0,n-1,0 #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j : m=(i+j)//2 if ls[m]==key: break elif ls[m]>key: j=m-1 else: i=m+1 if i<=j: print("查找到该值，位置为",m) else: print("查无此数") 如上述代码所示，变式和原式区别在于 变式去掉的用来标识有没有找到 key 的 flag 变量 计算可得 当 key 在当前数组 ls 中不存在时 i>j 即 i=j+1 ，当 key 存在于数组 中时 i<=j，所以在循环结束后 我们可以 通过 i和 j的关系来判断 key 是否存 在。 浙江高中技术培优算法（陶小波） 75 (3) 求大于等于 key 的第一个数 n=10#数的总数 ls=[1,2,2,2,2,2,2,2,2,3] key=2 i,j,m=0,n-1,0 #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j : m=(i+j)//2 if ls[m]>=key: j=m-1 else: i=m+1 print("连续数的第一个位置是",i) 如上述代码所示，变式和原式区别在于 变式去掉的用来标识有没有找到 key 的 flag 变量以及去掉了找到后退出的代码 即去掉了 break。 设 key 为 2 时 当 key 等于 ls[m]时,j 要往前走，一直走到第一个不是 2的位置， 即当前 1的位置时，i往后走 1，即 i=1,所以第一个数的位置是 i 初值 第一轮 第二轮 第三轮 m 0 4 1 0 i 0 0 0 1 j 9 3 0 0 浙江高中技术培优算法（陶小波） 76 (4) 求小于等于 key 的最后一个数 n=10#数的总数 ls=[1,2,2,2,2,2,2,2,2,3] key=2 i,j,m=0,n-1,0 #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j : m=(i+j)//2 if ls[m]>key: j=m-1 else: i=m+1 print("连续数的最后一个位置是",j) 如上述代码所示，变式和原式区别在于 变式去掉的用来标识有没有找到 key 的 flag 变量以及去掉了找到后退出的代码 即去掉了 break 表 3 设 key 为 2 时 当 key 等于 ls[m]时,i 要往后走，一直走到第一个不是 2的位置， 即当前 3的位置时，j往前走 1，即 j=8,所以最后一个数的位置是 j 初值 第一轮 第二轮 第三轮 第四轮 m 0 4 7 8 9 i 0 5 8 9 9 j 9 9 9 9 8 浙江高中技术培优算法（陶小波） 77 (5) 根据对分次数求 key 例：有如下代码，当 c等于 2的时候，key 有可能是多少？ import random c=0 n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=random.randint(20,40)#待查找的数 i,j,m,flag=0,n-1,0,False #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j and flag==False: c+=1 m=(i+j)//2 if ls[m]==key: flag=True break elif ls[m]>key: j=m-1 else: i=m+1 if flag: print("查找到该值，位置为",m) else: print("查无此数") 解：例如有数组长度为 10 的列表 其中值分别为 21, 25, 26, 29, 31, 33, 35, 37, 38, 39,通过画二分判定树（如下），可以很显然看到 c=2 的时候 就是对分 2次，即 key 有可能是 25 或 37 浙江高中技术培优算法（陶小波） 78 (6) 根据 i、j 变换求 key 例：有如下代码，当 c等于 1的时候，key 有可能是多少？ import random c=0 n=10#数的总数 ls=[random.randint(20,40) for i in range(n)]#生成随机数 ls.sort() #对数组进行升序排序 key=random.randint(20,40)#待查找的数 i,j,m,flag=0,n-1,0,False #i:起始位置游标，j:终止位置游标，m:当前对分到的位置，flag:是否查找到该 值 while i<=j and flag==False: m=(i+j)//2 if ls[m]==key: flag=True break elif ls[m]>key: j=m-1 c-=1 else: i=m+1 c+=1 if flag: print("查找到该值，位置为",m) else: print("查无此数") 解：例如有数组长度为 10 的列表 其中值分别为 21, 25, 26, 29, 31, 33, 35, 37, 38, 39,通过画二分判定树（如下），可以很显然看到 c=1 的时候 key 有可 能是 37 或 29 或 35 浙江高中技术培优算法（陶小波） 79 (7) 常见二分查找错误写法 有公共代码： n=10#数的总数 ls=[1,2,3,4,5,6,7,8,9,10] key=3 #待查找的数(例如查找 33) i,j,m=0,n-1,0 #i:起始位置游标，j:终止位置游标，m:当前对分到的位置 while i<=j : m=(i+j+1)//2 if ls[m]==key: break elif ls[m]>key: j=m-1 else: i=m 正确可以使用 while i<j : m=(i+j+1)//2 if ls[m]==key: break elif ls[m]>key: j=m-1 else: i=m 查询部分值位置正确，查询最左边的值 位置不正确 while i<j : m=(i+j)//2 if ls[m]==key: break elif ls[m]>key: j=m-1 else: i=m 循环可以进行，但位置查询不正确 while i<j : m=(i+j-1)//2 if ls[m]==key: break elif ls[m]>key: j=m else: i=m+1 查询部分值位置正确，查询最右边的值 位置不正确 while i<=j : m=(i+j-1)//2 if ls[m]==key: break elif ls[m]>key: j=m else: i=m+1 死循环 浙江高中技术培优算法（陶小波） 80 (8) 二分判定树绘制 有代码如下，其绘制判定树的办法是 ls=[22,33,44,55,66,77,88] i,j,m=0,6,0 while i<=j : m=(i+j)//2 if ls[m]==key: break elif ls[m]>key: j=m-1 else: i=m+1 第一步：确定中间位置（因为 i=0,j=6,可以推算出 m=3，即值为 55） 第二步：确定 55 左子树位置（因为 i=0,j=2,可以推算出 m=1，即值为 33） 第三步：确定 55 右子树位置（因为 i=4,j=6,可以推算出 m=5，即值为 77） 第四步：确定 33 左子树位置（因为 i=0,j=0,可以推算出 m=0，即值为 22） 浙江高中技术培优算法（陶小波） 81 第五步：确定 33 右子树位置（因为 i=2,j=2,可以推算出 m=2，即值为 44） 第六步：确定 77 左子树位置（因为 i=4,j=4,可以推算出 m=4，即值为 66） 第七步：确定 77 右子树位置（因为 i=6,j=6,可以推算出 m=6，即值为 88） 完成