專項(xiàng)代碼1 常見大題代碼合輯知識(shí)點(diǎn)梳理高考信息技術(shù)二輪復(fù)習(xí)知識(shí)點(diǎn)梳理

專項(xiàng)代碼1常見大題代碼合輯插入排序（通過鏈表實(shí)現(xiàn)）原理：第一步：先創(chuàng)建一個(gè)只有一個(gè)元素的鏈表。第二步：依次生成節(jié)點(diǎn)，再將節(jié)點(diǎn)放置到鏈表中指定位置。第三步：輸出鏈表節(jié)點(diǎn)。importrandom#插入排序（鏈表實(shí)現(xiàn)）[678,668,267,440,795]ls=[]#鏈表ls[0]是值，ls[1]是指針v=[random.randint(1,1000)foriinrange(5)]#待排序的數(shù)ls.append([v.pop(0),-1])#將第一個(gè)節(jié)點(diǎn)放入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]循環(huán)隊(duì)列（通過鏈表實(shí)現(xiàn)）原理：入隊(duì)：將節(jié)點(diǎn)添加到鏈表尾部（因?yàn)殛?duì)列從尾部進(jìn)入）出隊(duì)：刪除當(dāng)前頭節(jié)點(diǎn)（因?yàn)殛?duì)列出隊(duì)是從頭部出隊(duì)）importrandom#循環(huán)隊(duì)列功能（鏈表實(shí)現(xiàn)）ls=[]#鏈表ls[0]是值，ls[1]是指針head=0p=q=0foriinrange(1,6):#生成5個(gè)值的隊(duì)列l(wèi)s.append([i-1,i])ls[len(ls)-1][1]=0#將隊(duì)列最后一個(gè)指向第一個(gè)#出隊(duì)（出隊(duì)完成后還是一個(gè)圈）p=headwhilels[p][1]!=head:#找到最后一個(gè)節(jié)點(diǎn)p=ls[p][1]head=ls[head][1]ls[p][1]=head#入隊(duì)p=headwhilels[p][1]!=head:p=ls[p][1]ls.append([7,ls[p][1]])ls[p][1]=len(ls)-1數(shù)組插入（通過二分實(shí)現(xiàn)）將ls數(shù)組中的值，插入到ls2中指定位置，插入結(jié)束了ls2中的值依然有序原理:第一步:將原始值直接排序第二步:通過對(duì)分查找法查找到對(duì)應(yīng)的值插入的位置第三步:插入值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)#插入到數(shù)組中指定位置。第一個(gè)參數(shù)是位置第二個(gè)參數(shù)是值print(ls2)插入排序（for循環(huán)版本）importrandomn=5a=[random.randint(1,100)foriinrange(n)]#生成隨機(jī)數(shù)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]計(jì)數(shù)排序（通過雙重循環(huán)實(shí)現(xiàn)）importrandomn=5a=[random.randint(1,100)foriinrange(n)]#生成隨機(jī)數(shù)[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)#排序后的結(jié)果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