第14章（排序含代码）知识点梳理高考信息技术二轮复习知识点梳理

第十四章(排序)考纲中的排序包括冒泡排序，选择排序。但是在实际解题中还会碰到其他排序，例如桶排序、插入排序、选择排序、索引排序及冒泡排序的优化。本文将针对冒泡、选择、插入、选择排序、桶排序、索引排序及冒泡排序优化进行分析。升序排：从小到大排序，降序排：从大到小排序冒泡排序冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序比较次数(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冒泡优化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冒泡优化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]选择排序写法1foriinrange(n-1):forjinrange(i+1,n):ifls[i]>ls[j]:ls[i],ls[j]=ls[j],ls[i]选择排序写法2表1.3桶排序桶排序(Bucketsort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）n=10ls=[random.randint(1,100)foriinrange(n)]#生成随机数bucket=[0]*101#新建一个范围在[0,100]之间的桶foriinls:#入桶bucket[i]+=1foriinrange(1,100):#出桶forjinrange(bucket[i]):print(i,end=",")插入排序插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动importrandomj=0n=5a=[random.randint(1,100)foriinrange(n)]#生成随机数foriinrange(0,n):key=a[i]j=i-1whilej>=0andkey<a[j]:a[j+1]=a[j]j=j-1a[j+1]=key索引排序索引排序，是基于冒泡排序法的一种优化算法，算法核心是:用一个数组元素的值做另一个数组元素的下标，然后交换下标。例如a[b[1]]<a[b[2]]:t=b[1]:b[1]=b[2]:b[2]=t。代码如下：importrandomn=10ls=[random.randint(1,100)foriinrange(n)]#生成随机数xb=[iforiinrange(n)]fori