數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)（五）【知識(shí)要點(diǎn)】冒泡排序（要求：熟練掌握）工作原理：每次檢查相鄰兩個(gè)元素，如果前后元素不滿足升序(降序)就將相鄰兩個(gè)元素交換，當(dāng)沒(méi)有相鄰元素需要交換時(shí)，排序就完成了。經(jīng)i輪排序掃描，第i大(小)的數(shù)會(huì)被冒泡到數(shù)列的前面或后面2)穩(wěn)定性：冒泡排序是一種穩(wěn)定的排序算法3)時(shí)間復(fù)雜度：O(n2)defbubble_sort(a):#冒泡排序(升序)

foriinrange(1,len(a)):

#比較輪數(shù)=len1

forjinrange(len(a)i):#當(dāng)前比較位置

ifa[j]>a[j+1]:

a[j],a[j+1]=a[j+1],a[j]

returnaa=[7,8,0,1,6,3,9,4,5,2]print(bubble_sort(a))我們發(fā)現(xiàn)最后兩輪冒泡時(shí)已經(jīng)有序，可以直接退出循環(huán)以提升算法效率defbubble_sort(a):#冒泡排序優(yōu)化

foriinrange(1,len(a)):

#比較輪數(shù)=len1

flag=True#flag初始狀態(tài)

forjinrange(len(a)i):

#當(dāng)前比較位置

ifa[j]>a[j+1]:

a[j],a[j+1]=a[j+1],a[j]

flag=False#發(fā)生交換則標(biāo)記flag

ifflag:break#若一輪都未發(fā)生交換則說(shuō)明已經(jīng)有序

returnaa=[7,8,0,1,6,3,9,4,5,2]print(bubble_sort(a))選擇排序（要求：熟練掌握）工作原理：每次找出第i小(大)的元素，然后將這個(gè)元素和第i個(gè)位置元素交換2)穩(wěn)定性：一般的認(rèn)為選擇排序是一種不穩(wěn)定的算法3)時(shí)間復(fù)雜度：O(n2)defselection_sort(a):#選擇排序(升序)

foriinrange(len(a)1):

ith=i

forjinrange(i+1,len(a)):

ifa[ith]>a[j]:

ith=j

#找到第i小的值位置

a[ith],a[i]=a[i],a[ith]

returnaa=[6,7,5,8,2,1,4,0,3,9]print(selection_sort(a))插入排序（要求：熟練掌握）工作原理：將待排元素分為“已排序”和“未排序”兩個(gè)部分，每次從未排序部分中取出一個(gè)元素放到已排序中。穩(wěn)定性：插入排序是一種穩(wěn)定的算法時(shí)間復(fù)雜度：最優(yōu)O(n)，最差O(n2)definsertion_sort(a):#插入排序(升序)

foriinrange(1,len(a)):

#小于i的為有序部分,i~len1為無(wú)序部分

val=a[i]

#無(wú)序部分取值

pos=i1

whilepos>=0anda[pos]>val:

#在有序部分尋找插入位置

a[pos+1]=a[pos]

#逐位后移

pos=1

a[pos+1]=val

#將值插入有序部分

returnaa=[6,0,9,5,8,3,4,7,1,2]print(insertion_sort(a))桶排序（要求：理解運(yùn)行過(guò)程）工作原理：桶排序也并非常規(guī)的排序算法，它實(shí)際上是一種分治思想的實(shí)踐。桶排序的過(guò)程可以分為4步：1.根據(jù)數(shù)據(jù)的特征將數(shù)據(jù)分為若干的桶，給每個(gè)桶規(guī)定可以存儲(chǔ)的值的范圍；2.將原數(shù)列的數(shù)據(jù)放入各個(gè)桶中；3.對(duì)每個(gè)桶都進(jìn)行排序；4.按照桶的順序?qū)⑼皟?nèi)數(shù)據(jù)重新鏈接。注意區(qū)分桶排序，歸并排序，快速排序的區(qū)別。2)穩(wěn)定性：桶排序的穩(wěn)定性取決與其內(nèi)層排序的排序算法3)時(shí)間復(fù)雜度：O(n2)#桶排序defbucket_sort(a):

bucket=[]

b=[]

bucketnum=(max(a)min(a))//len(a)+1#根據(jù)數(shù)據(jù)特征確定桶數(shù)量

foriinrange(bucketnum):

#建桶

bucket.append([])

forxina:#入桶

num=(xmin(a))//len(a)

bucket[num].append(x)

foriinrange(bucketnum):

bucket[i].sort()

#并非“脫了褲子放屁”，詳見“注意”

b.extend(bucket[i])

#與b+=bucket[i]等價(jià)

print(bucket)#輸出桶結(jié)構(gòu)

returnba=[77,7,26,14,11,21,60,51,30,78]print(bucket_sort(a))#運(yùn)行結(jié)果[[7,11,14],[21,26],[30],[],[51],[60],[],[77,78]]#桶結(jié)構(gòu)[7,11,14,21,26,30,51,60,77,78]注意：桶排序更多適用與數(shù)據(jù)值域較大但分別較均勻的情況，其本質(zhì)也只是用于分段，對(duì)于桶內(nèi)數(shù)據(jù)一般不會(huì)再使用桶排序遞歸，而是采用更高效的排序算法。故示例再桶內(nèi)排序時(shí)也直接使用了sort()方法加以區(qū)分和說(shuō)明。歸并排序（要求：理解運(yùn)行過(guò)程）1)工作原理：歸并排序是一種采用“分治思想”的排序方法。歸并排序分為三個(gè)步驟：1.將數(shù)列分成左右兩個(gè)部分；2.對(duì)左右兩個(gè)部分進(jìn)行并歸排序；3.合并兩個(gè)子序列。不難看出，并歸中含有遞歸思想。2)穩(wěn)定性：并歸排序是一種穩(wěn)定的排序算法3)時(shí)間復(fù)雜度：O(nlogn)4)空間復(fù)雜度：O(n)defmerge(a,left,mid,right):

#歸并排序(升序)#兩個(gè)有序數(shù)組合并(含頭不含尾)

i=left;j=mid

b=[]

whilei<midandj<right:

ifa[i]<a[j]:

b.append(a[i]);i+=1

else:

b.append(a[j]);j+=1

whilei<mid:

b.append(a[i]);i+=1

whilej<right:

b.append(a[j]);j+=1

a[left:right]=b

#整理后復(fù)制回原數(shù)組

returnadefmerge_sort(a,left,right):

#歸并(含頭不含尾)

ifleft<right1:#子序列長(zhǎng)度不為1

mid=(left+right)//2

a=merge_sort(a,left,mid)#歸并左數(shù)列

a=merge_sort(a,mid,right)#歸并右數(shù)列

a=merge(a,left,mid,right)#左右數(shù)列合并

returnaa=[8,0,2,5,9,7,3,4,6,1]print(merge_sort(a,0,len(a)))快速排序（要求：理解運(yùn)行過(guò)程）1)工作原理：快速排序和歸并排序類似，都采用了分治思想?？焖倥判蛞部梢苑譃槿齻€(gè)步驟：1.找一個(gè)值為基值，然后將小于基值的數(shù)放到基值左邊，大于基值的數(shù)放到基值；2.對(duì)基值左右兩部分再次進(jìn)行快速排序；3.左右數(shù)列不需要合并已經(jīng)有序。顯然，快速排序也基于遞歸思想。2)穩(wěn)定性：快速排序是一種不穩(wěn)定的排序算法3)時(shí)間復(fù)雜度：最優(yōu)O(nlogn)，最次O(n2)defpartition(a,low,hight):

#快速排序(升序)分段(左索引,右索引)

pivot_num=a[low]

#獲取基值

whilelow<hight:

whilelow<hightanda[hight]>=pivot_num:

hight=1

a[low]=a[hight]

#比基值大的放在基值左側(cè)

whilelow<hightanda[low]<=pivot_num:

low+=1

a[hight]=a[low]

#比基值小的放在基值右側(cè)

pivot=low

a[pivot]=pivot_num

returna,pivot

#返回更新完的數(shù)列和基值位置defquick_sort(a,low,hight):

#快速排序(左索引,右索引)

iflow>=hight:

returna

a,pivot=partition(a,low,hight)

#將數(shù)組分為兩個(gè)部分

a=quick_sort(a,low,pivot1)

#遞歸排序左半部分

a=quick_sort(a,pivot+1,hight)

#遞歸排序右半部分

returnaa=[5,4,8,3,6,2,9,1,7,0]print(quick_sort(a,0,len(a)1))希爾排序(縮小增量排序)（要求：在掌握插入排序基礎(chǔ)上能夠自主運(yùn)用）1)工作原理：希爾排序是插入排序的一種改進(jìn)版本，以其發(fā)明者希爾命名。希爾排序主要分三步處理排序問(wèn)題：1.將待排序序列分為若干子序列；2.對(duì)子序列中相同位置的數(shù)進(jìn)行插入排序；3.縮小每個(gè)子序列元素間的間距，重復(fù)過(guò)程直至間距縮小為1。2)穩(wěn)定性：希爾排序是一種不穩(wěn)定的排序算法。3)時(shí)間復(fù)雜度：希爾排序的時(shí)間復(fù)雜度和縮小間距的選取有之間關(guān)系。4)空間復(fù)雜度：O(n)defshell_sort(a):#希爾排序

delta=len(a)//2#間距

whiledelta>=1:

foriinrange(delta,len(a),1):

j=i

whilej>=deltaanda[j]<a[jdelta]:

#兩個(gè)條件同時(shí)滿足時(shí),根據(jù)步長(zhǎng)交換,使后面的較小數(shù)快速前移

a[j],a[jdelta]=a[jdelta],a[j]

j=delta#跳到前一組繼續(xù)比較

delta//=2#調(diào)整間距

returnaa=[8,5,3,4,0,7,9,1,2,6]print(shell_sort(a))計(jì)數(shù)排序（要求：理解運(yùn)行過(guò)程）1)工作原理：計(jì)數(shù)排序與常規(guī)排序不同，它使用一個(gè)額外的數(shù)組（或字典）去存儲(chǔ)各個(gè)數(shù)據(jù)的個(gè)數(shù)，然后根據(jù)數(shù)組（或字典）中值的大小順序重新復(fù)原數(shù)組。2)穩(wěn)定性：計(jì)數(shù)排序是一種穩(wěn)定的排序算法3)時(shí)間復(fù)雜度：計(jì)數(shù)排序的時(shí)間復(fù)雜度O(n)defcount_sort(a):#計(jì)數(shù)排序dic={};b=[]foriina:dic[i]=dic.get(i,0)+1#注意get()方法的使用forjinrange(min(a),max(a)+1):ifdic.get(j,0)>0:forkinrange(dic[j]):b.append(j)#print(dic)#用于輸出字典結(jié)果，實(shí)際中不需要returnba=[9,8,3,5,1,4,9,6,4,4]print(count_sort(a))#運(yùn)行結(jié)果{9:2,8:1,3:1,5:1,1:1,4:3,6:1}[1,3,4,4,4,5,6,8,9,9]注意：get(鍵,填充值)方法的使用，避免了字典查詢?yōu)榭盏膯?wèn)題min()，max()方法的使用有點(diǎn)取巧，最值應(yīng)該在第一次循環(huán)存字典時(shí)順帶統(tǒng)計(jì)。字典是一種無(wú)序結(jié)構(gòu)，重新整合數(shù)組順序由j循環(huán)控制基數(shù)排序（要求：理解運(yùn)行過(guò)程）工作原理：基數(shù)排序是一種非比較排序算法，最早用與解決卡片排序問(wèn)題。基數(shù)排序的過(guò)程：將待排序元素按位拆分，然后先排個(gè)位，再排十位，再排百位......對(duì)最高位排序結(jié)束后序列已經(jīng)有序。2)穩(wěn)定性：基數(shù)排序是一種穩(wěn)定的排序算法3)時(shí)間復(fù)雜度：O(nklogn)4)空間復(fù)雜度：O(n)defradix_sort(a):#基數(shù)排序max_len=len(str(max(a)))foriinrange(1,max_len1,1):#位數(shù)循環(huán)b=[]bucket=[[]foriinrange(10)]#建桶，09共10個(gè)數(shù)forjina:try:radix=int(str(j)[i])#關(guān)鍵字，即個(gè)位，十位......except:radix=0bucket[radix].append(j)#print(bucket)forkinrange(10):#出桶iflen(bucket[k])>0:b.extend(bucket[k])#與b+=bucket[k]等價(jià)a=b#print(a)returnaa=[100,82,6,33,84,28,41,64,89,61]print(radix_sort(a))#運(yùn)行結(jié)果：[100,82,6,33,84,28,41,64,89,61][[100],[41,61],[82],[33],[84,64],[],[6],[],[28],[89]]#第一次，個(gè)位入桶[100,41,61,82,33,84,64,6,28,89]#第一次結(jié)果[[100,6],[],[28],[33],[41],[],[61,64],[],[82,84,89],[]]#第二次十位入桶[100,6,28,33,41,61,64,82,84,89]#第二次結(jié)果[[6,28,33,41,61,64,82,84,89],[100],[],[],[],[],[],[],[],[]]#第三次百位入桶[6,28,33,41,61,64,82,84,89,100]#第三次結(jié)果堆排序（要求：了解即可）1)工作原理：堆排序使用了滿二叉樹結(jié)構(gòu)（堆結(jié)構(gòu)）盡心排序。首先將一維數(shù)列轉(zhuǎn)為一個(gè)滿二叉樹（即父節(jié)點(diǎn)的索引i和子節(jié)點(diǎn)的索引j，滿足j=i*2+1）,然后進(jìn)行最大（?。┒颜{(diào)整。每次調(diào)整后根節(jié)點(diǎn)一定是最大（?。┲?，將根節(jié)點(diǎn)輸出后堆剩余部分再進(jìn)行最大（小）堆調(diào)整。2)穩(wěn)定性：堆排序是一種不穩(wěn)定的算法3)時(shí)間復(fù)雜度：O(nlogn)defmax_heapify(a,start,end):

#堆排序

最大堆調(diào)整

dad=start

#父節(jié)點(diǎn)

son=dad*2+1

#左子節(jié)點(diǎn)

whileson<=end:

#子節(jié)點(diǎn)索引不越界

ifson+1<=endanda[son]<a[son+1]:

#先比較左右子節(jié)點(diǎn)

son+=1

#若右節(jié)點(diǎn)更大，則交換節(jié)點(diǎn)更新為右節(jié)點(diǎn)

ifa[dad]<a[son]:

a[dad],a[son]=a[son],a[dad]

dad=son

son=dad*2+1

else:

breakreturnadefheap_sort(a):

#初始化調(diào)整，從最后一個(gè)父節(jié)點(diǎn)開始

foriinrange(len(a)//21,1,1):

a=max_heapify(a,i,len(a)1)

#最大堆的根節(jié)點(diǎn)一定是最大值，將最后一個(gè)節(jié)點(diǎn)替換根節(jié)點(diǎn)后再次排序

foriinrange(len(a)1,0,1):

a[0],a[i]=a[i],a[0]

a=max_heapify(a,0,i1)

returnaa=[5,1,9,6,8,7,2,0,3,4]print(heap_sort(a))【例題剖析】1.有如下Python程序段：b＝[56，78，11，31，24，52，66，49]count＝len(b)foriinrange(1,3)：forjinrange(0，count－i)：ifb[j]>b[j＋1]：b[j]，b[j＋1]＝b[j＋1]，b[j]經(jīng)過(guò)該程序段“加工”后，列表b中的元素為()A.[11,24,31,52,49,56,66,78] B.[11,31,24,52,56,49,66,78]C.[56,11,31,24,52,66,49,78] D.[11,24,31,52,49,56,66,78]答案B解析本題主要考查的冒泡排序算法的程序?qū)崿F(xiàn)。該程序段的功能是：采用冒泡排序算法進(jìn)行升序排序2遍，數(shù)據(jù)比較是從前往后進(jìn)行的，第1遍排序后列表b中的元素為[56,11,31,24,52,66,49,78]，第2遍排序后的數(shù)據(jù)序列為[11,31,24,52,56,49,66,78]，因此答案為B。2.有如下Python程序段：Ls＝["LiMing"，"WangPeng"，"ShengYi"，"ShaDan"，"XiaPo"，"ManGao"]n＝len(Ls)foriinrange(1，3)：forjinrange(0，n－i)：ifLs[j]<Ls[j＋1]：Ls[j]，Ls[j＋1]＝Ls[j＋1]，Ls[j]print("排序后的序列為："，Ls)經(jīng)過(guò)該程序段“加工”后，列表Ls中的元素為()A.['LiMing','XiaPo','WangPeng','ShengYi','ShaDan','ManGao']B.['WangPeng','XiaPo','ShengYi','ShaDan','ManGao','LiMing']C.['WangPeng','ShengYi','XiaPo','ShaDan','ManGao','LiMing']D.['WangPeng','ShengYi','ShaDan','XiaPo','ManGao','LiMing']答案C解析本程序的功能是顯示從左往右進(jìn)行2趟降序排序后的數(shù)據(jù)序列，第1趟排序后的數(shù)據(jù)序列為"WangPeng"，"ShengYi"，"ShaDan"，"XiaPo"，"LiMing"，"ManGao"，第2趟排序后的數(shù)據(jù)序列為"WangPeng"，"ShengYi"，"XiaPo"，"ShaDan"，"LiMing"，"ManGao"。因此，答案為C?！玖?xí)題鞏固】1.有如下python程序段:a=[1]*6b=[96,88,84,91,99,80]foriinrange(6):forjinrange(i+1,6):ifb[j]>b[i]:a[i]+=1else:a[j]+=1該程序段運(yùn)行后，列表a的值為（）A.[5,3,2,4,6,1]B.[2,4,5,3,1,6]C.[10,6,4,8,12,2]D.[4,8,10,6,2,12]2.有如下python程序段:lst=[74,32,66,46,38,28,85]k=1foriinrange(len(lst)1):iflst[i]*k<lst[i+1]*k:print(lst[i],end="")k=k執(zhí)行完以上程序段后，輸出的內(nèi)容為()A.746638B.7432663828C.743266463828D.463.有如下python程序段:a=[int(i)forininput("請(qǐng)輸入:").split()]#將以空格隔開的輸入數(shù)以列表的形式存儲(chǔ)m=len(a)whilem!=1;foriinrange(m1):ifa[i]>a[i+1]:a[i],a[i+1]=a[i+1],a[i]m=1print(a)執(zhí)行程序后，輸入的數(shù)字為3196，輸出的結(jié)果為()A.[1,3,6,9]B.[9,6,3,1]C.[1,6,3,9]D.[9,3,6,1]4.有如下python程序段:fromrandomimportrandintlist=[0]*6foriinrange(6):list[i]=randint(10,99)foriinrange(2):forjinrange(5i):iflist[j]//10+list[j]%10>list[j+1]//10+list[j+1]%10:list[j],list[j+1]=list[j+1],list[j]print(list)該程序段運(yùn)行后，列表list的值不可能為（）A.[54,17,26,40,73,85]B.[10,36,81,60,84,69]C.[33,81,15,46,19,69]D.[10,22,31,67,72,99]5.現(xiàn)有n個(gè)學(xué)生的7門學(xué)科成績(jī)已存入一維數(shù)組cj中。某python程序代碼段如下:deff(x):p=x*7;k=0forjinrange(7):ifcj[p+j]>cj[p+k]:k=jreturn(k)km="物化生政史地技"n=2;s=""foriinrange(n):s+=km[f(i)]print(s)cj數(shù)組元素的值依次為96,83,91,85,86,77,88,98,93,94,82,96,87,99,運(yùn)行后,輸出的結(jié)果為（）A.物技B.地政C.物生D.技物6.以下程序希望能實(shí)現(xiàn)隨機(jī)序列的升序(從小到大)排列，則劃線部分程序正確的是()importrandomarr=[]foriinrange(10):t=random.randint(1,100)arr.append(t)foriinrange(1,len(arr)):key=arr[i]j=ilwhile____①____:arr[j+1]=arr[j]j=l____②____print("排序后的數(shù)組:")foriinrang(len(arr)):print("%d"%arr[i])#依次輸出ar中的每個(gè)元素A.①j>=0andkey<arr[j]②arr[j+1]=keyB.①j>=0andkey<arr[j]②arr[j]=keyC.①j>=0andkey>arr[j]②arr[j]=keyD.①j>=0andkey>arr[i]②arr[j+1]=key7.有如下Python程序段:La=["orange","banana","apple","grape","pear","mango"]count=len(La)foriinrange(0,2):forjinrange(count1,i,1):ifLa[j]<La[j1]:La[j],La[j1]=La[j1],La[j]經(jīng)過(guò)該程序段“加工”后,列表La的元素為()A.["apple","orange","banana","grape","mango","pear"]B.["apple","banana","orange","grape","mango","pear"]C.["apple","banana","grape","orange","mango","pear"]D.["apple","banana","grape","mango","orange","pear"]8.小李基于冒泡排序算法編寫了一個(gè)VB程序,功能如下:輸入若干個(gè)待排序的數(shù)據(jù),輸出刪除重復(fù)數(shù)據(jù)后的升序排序結(jié)果。程序運(yùn)行示例如圖所示。實(shí)現(xiàn)上述功能的VB程序如下,請(qǐng)回答下列問(wèn)題:L2=input("Pleaseinputnumber:").split(",")print(L2)n=len(L2)foriinrange(0,n):L2[i]=eval(L2[i])bottom=n1i=0whilei<=bottom2:forjinrange(bottom,i,1):ifL2[j]<L2[i]:L2[j],L2[j1]=L2[j1],L2[j]elifL2[j]==L2[j1]:____①____bottom=bottom1i=i+1print("排序后的數(shù)據(jù)為:",____②____)(1)加框處的代碼有誤碼，請(qǐng)改正。(2)請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。9.小明基于冒泡排序思想設(shè)計(jì)了一個(gè)改進(jìn)的排序算法。該算法先用冒泡法將列表b中奇數(shù)位置的元素、偶數(shù)位置的元素分別進(jìn)行排序，然后再進(jìn)行后續(xù)處理。算法的Python程序段如下，請(qǐng)回答下列問(wèn)題。b=[26,12,30,23,32,28,49,35,38]n=len(b)foriinrange(1,(n+1)//2):forjinrange(0,ni*2):if①________________:b[j],b[j+2]=b[j+2],b[j]foriinrange(1,n//2+1):j=2*i1ifb[j]<b[j1]:b[j],b[j1]=b[j1],b[j]foriinrange(1,n):t=b[i]j=i1whilet<b[j]:b[j+1]=b[j]j=1②____________________print("處理后的數(shù)據(jù)序列為：",b)(1)加框處的代碼有誤，請(qǐng)改正。(2)請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。10.小明為了研究冒泡排序過(guò)程中數(shù)據(jù)的“移動(dòng)”情況，編寫了一個(gè)Python程序，功能如下：第一行顯示排序前的數(shù)據(jù)，輸入初始位置(即下標(biāo)值)后，輸出指定初始位置的數(shù)據(jù)在排序過(guò)程中的位置變化情況，最后一行輸出排序后的數(shù)據(jù)。程序運(yùn)行示例如下圖所示。請(qǐng)輸入初始位置(索引值)：2排序前數(shù)據(jù)序列為：[43，23，65，12，26，33，58，19]位置變化情況：2→1→0排序后的數(shù)據(jù)序列為：[65，58，43，33，26，23，19，12]實(shí)現(xiàn)上述功能的Python程序如下，請(qǐng)回答下列問(wèn)題。a＝[43，23，65，12，26，33，58，19]n＝len(a)pos＝int(input("請(qǐng)輸入初始位置(索引值)："))①________________print("排序前數(shù)據(jù)序列為："，a)foriinrange(1，n)：forjinrange(0，n－i)：if②________________：a[j]，a[j＋1]＝a[j＋1]，a[j]ifpos＝＝j(luò)：pos＝j(luò)＋1s＝s＋"→"＋str(pos)elif③____________________：pos＝j(luò)s＝s＋"→"＋str(pos)print("位置變化情況："＋s)print("排序后的數(shù)據(jù)序列為："，a)(1)請(qǐng)?jiān)诔绦騽澗€處填入合適的代碼。(2)程序運(yùn)行樣例如圖所示，若輸入的初始位置(索引值)為4，則輸出的位置變化情況為____________________。11.某分段排序算法描述如下:1)將原始數(shù)據(jù)按非降序(a[1]<=a[2]<=a[3].....)分成兩個(gè)有序段。2)將兩個(gè)有序段進(jìn)行合并，使得合并后的數(shù)據(jù)依舊有序，得到新的非降序段。如原始數(shù)據(jù):1,3,4,5,7,9,2,6合并后結(jié)果:1,2,3,4,5,6,7,9編寫Python程序，實(shí)現(xiàn)分段排序功能:讀取“數(shù)據(jù).txt”文件，如圖所示，文件中每行有兩段非降序數(shù)據(jù)，將每一行處理成一段非降序數(shù)據(jù)。請(qǐng)回答下列問(wèn)題:(1)請(qǐng)?jiān)跈M線處填入合適的代碼。(2)方框內(nèi)為錯(cuò)誤代碼，請(qǐng)改正。(3)如果某一行的數(shù)據(jù)為“7,7,9,17,25,25”,則虛線框處代碼執(zhí)行后，k的值為 。#按行讀取“數(shù)據(jù).txt”文件，每次讀一行文字存入字符串變量line中

f=open("數(shù)據(jù).txt")

line=f.readline()

whileline:

sj=line.split(",")

#將字符串以”,”為間隔分割成多個(gè)字符串組成的列表

a=[0]*len(sj);b=[0]*len(sj)

foriinrange(len(sj)):

a[i]=①

k=0

forkinrange(len(a)1):

ifa[k]>a[k+1]:

break

else:

k=len(a)1

p=k

j=②

t=0;i=0

whilei<p+1orj<len(a):

ifj>=len(a)ori<panda[j]<a[i]:

b[t]=a[i];i=i+1

else:

b[t]=a[j];j=j+1

③

print(b)

line=f.readline()#讀取下一行

f.close()12.學(xué)校為校慶選拔節(jié)目,每個(gè)班級(jí)先到A場(chǎng)地做“準(zhǔn)備",然后到B場(chǎng)地“演出”。同一場(chǎng)地,同一時(shí)間只允許一個(gè)班級(jí)使用。每個(gè)班級(jí)使用A,B場(chǎng)地時(shí)間都有所不同。已知學(xué)校共n個(gè)班級(jí),第i個(gè)班級(jí)使用A場(chǎng)地時(shí)長(zhǎng)為a[i]分鐘,使用B場(chǎng)地時(shí)長(zhǎng)為b[i]分鐘。為了更高效的組織這次選拔活動(dòng)，某同學(xué)編寫了如下Python程序計(jì)算此次活動(dòng)的最小總時(shí)長(zhǎng)和班級(jí)參加選拔的順序。算法思路如下:1.統(tǒng)計(jì)m[i]表示第i個(gè)班級(jí)中在A和B兩個(gè)場(chǎng)地中用時(shí)的較小值2.按m[i]值從小到大排序,然后按m[i]值的順序,逐個(gè)班級(jí)安排參選順序,策略如下:為了使得總時(shí)長(zhǎng)最短,讓A場(chǎng)地用時(shí)最少的最先開始;B場(chǎng)地用時(shí)最少的最后開始。對(duì)于每個(gè)班級(jí),若m[i]與該班級(jí)在A場(chǎng)地使用時(shí)間相同,則將它排在剩余的可排位置的最前面,若m[i]與該班級(jí)B場(chǎng)地使用的時(shí)間相等,則將它安排在剩余可排位置的最后面。例如:n=5,班級(jí)序號(hào)分別是{1,2,3,4,5}1至5號(hào)班級(jí)使用A場(chǎng)地的時(shí)間依次為:{3