专项代码1 常见大题代码合辑知识点梳理高考信息技术二轮复习知识点梳理

专项代码1常见大题代码合辑插入排序（通过链表实现）原理：第一步：先创建一个只有一个元素的链表。第二步：依次生成节点，再将节点放置到链表中指定位置。第三步：输出链表节点。importrandom#插入排序（链表实现）[678,668,267,440,795]ls=[]#链表ls[0]是值，ls[1]是指针v=[random.randint(1,1000)foriinrange(5)]#待排序的数ls.append([v.pop(0),-1])#将第一个节点放入head=0p=q=0whilelen(v)!=0:p=q=headwhilep!=-1andls[p][0]>v[0]:q=pp=ls[p][1]ifp!=head:#不放在链表头上ls.append([v.pop(0),ls[q][1]])ls[q][1]=len(ls)-1else:#放在链表头上ls.append([v.pop(0),head])head=len(ls)-1p=headwhilep!=-1:print(ls[p][0])p=ls[p][1]循环队列（通过链表实现）原理：入队：将节点添加到链表尾部（因为队列从尾部进入）出队：删除当前头节点（因为队列出队是从头部出队）importrandom#循环队列功能（链表实现）ls=[]#链表ls[0]是值，ls[1]是指针head=0p=q=0foriinrange(1,6):#生成5个值的队列ls.append([i-1,i])ls[len(ls)-1][1]=0#将队列最后一个指向第一个#出队（出队完成后还是一个圈）p=headwhilels[p][1]!=head:#找到最后一个节点p=ls[p][1]head=ls[head][1]ls[p][1]=head#入队p=headwhilels[p][1]!=head:p=ls[p][1]ls.append([7,ls[p][1]])ls[p][1]=len(ls)-1数组插入（通过二分实现）将ls数组中的值，插入到ls2中指定位置，插入结束了ls2中的值依然有序原理:第一步:将原始值直接排序第二步:通过对分查找法查找到对应的值插入的位置第三步:插入值importrandomls=[random.randint(1,100)foriinrange(5)]ls2=[random.randint(1,100)foriinrange(10)]ls.sort()ls2.sort()forkinls:i,j,m=0,len(ls2)-1,0whilei<=j:m=(i+j)//2ifk<ls2[m]:j=m-1else:i=m+1ls2.insert(i,k)#插入到数组中指定位置。第一个参数是位置第二个参数是值print(ls2)插入排序（for循环版本）importrandomn=5a=[random.randint(1,100)foriinrange(n)]#生成随机数foriinrange(n):key=a[i]forjinrange(i-1,-2,-1):ifkey>=a[j]:breakelse:a[j+1]=a[j]a[j+1]=keyprint(a)[16,65,2,33,11]计数排序（通过双重循环实现）importrandomn=5a=[random.randint(1,100)foriinrange(n)]#生成随机数[82,43,60,27,30]ls=[0]*nforiinrange(n):forjinrange(n):ifa[i]<a[j]:ls[i]+=1print(a)so=[]k=0whilelen(so)!=len(a):ifls[k]==max(ls):so.append(a[k])ls[k]=-1k=(k+1)%len(a)print(so)#排序后的结果foriinrange(len(ls)):ifls[i]==len(ls)-1:print("最小值是",a[i])ifls[i]==0:print("最大值是",a[i])快速排序（递归版本）defpartition(arr,low,high):i=(low-1)pivot=arr[high]forjinrange(low,high):ifarr[j]<=pivot:i=i+1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1defquickSort(arr,low,high):iflow<high:pi=partition(arr,low,high)quickSort(arr,low,pi-1)quickSo