第14章（排序含代碼）知識點梳理高考信息技術(shù)二輪復(fù)習知識點梳理

第十四章(排序)考綱中的排序包括冒泡排序，選擇排序。但是在實際解題中還會碰到其他排序，例如桶排序、插入排序、選擇排序、索引排序及冒泡排序的優(yōu)化。本文將針對冒泡、選擇、插入、選擇排序、桶排序、索引排序及冒泡排序優(yōu)化進行分析。升序排：從小到大排序，降序排：從大到小排序冒泡排序冒泡排序算法是把較小的元素往前調(diào)或者把較大的元素往后調(diào)。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據(jù)比較結(jié)果和算法規(guī)則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序比較次數(shù)(n*(n-1))/2有如下公共代碼：importrandomls=[]n=5foriinrange(n):ls.append(random.randint(10,100))foriinrange(n-1):forjinrange(n-1,i,-1):ifls[j]>ls[j-1]:ls[j]=ls[j]+ls[j-1]ls[j-1]=ls[j]-ls[j-1]ls[j]=ls[j]-ls[j-1]降序排(從后往前冒泡）foriinrange(n-1):forjinrange(n-1,i,-1):ifls[j]<ls[j-1]:ls[j]=ls[j]+ls[j-1]ls[j-1]=ls[j]-ls[j-1]ls[j]=ls[j]-ls[j-1]升序排(從后往前冒泡） 表1.1foriinrange(n-1):forjinrange(0,n-i-1):ifls[j]>ls[j+1]:ls[j]=ls[j]+ls[j+1]ls[j+1]=ls[j]-ls[j+1]ls[j]=ls[j]-ls[j+1]升序排(從前往后冒泡）foriinrange(n-1):forjinrange(1,n-i):ifls[j]>ls[j-1]:ls[j]=ls[j]+ls[j-1]ls[j-1]=ls[j]-ls[j-1]ls[j]=ls[j]-ls[j-1]降序排(從前往后冒泡）foriinrange(n-1):flag=Falseforjinrange(n-1,i,-1):ifls[j]>ls[j-1]:ls[j]=ls[j]+ls[j-1]ls[j-1]=ls[j]-ls[j-1]ls[j]=ls[j]-ls[j-1]Flag=TrueIfflag==False：break冒泡優(yōu)化1k=n-1last=0foriinrange(n-1):flag=Trueforjinrange(k):ifls[j]>ls[j+1]:ls[j]=ls[j]+ls[j+1]ls[j+1]=ls[j]-ls[j+1]ls[j]=ls[j]-ls[j+1]last=jflag=Falsek=lastifflag:break冒泡優(yōu)化2 表1.2選擇排序選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了。有如下公共代碼：importrandomls=[]n=5foriinrange(n):ls.append(random.randint(10,100))foriinrange(n-1):k=iforjinrange(i+1,n):ifls[j]<ls[k]:k=jifk!=i:ls[k],ls[i]=ls[i],ls[k]選擇排序?qū)懛?foriinrange(n-1):forjinrange(i+1,n):ifls[i]>ls[j]:ls[i],ls[j]=ls[j],ls[i]選擇排序?qū)懛?表1.3桶排序桶排序(Bucketsort)或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）n=10ls=[random.randint(1,100)foriinrange(n)]#生成隨機數(shù)bucket=[0]*101#新建一個范圍在[0,100]之間的桶foriinls:#入桶bucket[i]+=1foriinrange(1,100):#出桶forjinrange(bucket[i]):print(i,end=",")插入排序插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的、記錄數(shù)增1的有序表。在其實現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找，并進行移動importrandomj=0n=5a=[random.randint(1,100)foriinrange(n)]#生成隨機數(shù)foriinrange(0,n):key=a[i]j=i-1whilej>=0andkey<a[j]:a[j+1]=a[j]j=j-1a[j+1]=key索引排序索引排序，是基于冒泡排序法的一種優(yōu)化算法，算法核心是:用一個數(shù)組元素的值做另一個數(shù)組元素的下標，然后交換下標。例如a[b[1]]<a[b[2]]:t=b[1]:b[1]=b[2]:b[2]=t。代碼如下：importrandomn=10ls=[random.randint(1,100)foriinrange(n)]#生成隨機數(shù)xb=[iforiinrange(n)]fori