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

第十四章 (排序) 考纲中的排序包括冒泡排序，选择排序。但是在实际解题中还会碰到其他排序，例如桶排序、插入排序、选择排序、索引排序及冒泡排序的优化。本文将针对冒泡、选择、插入、选择排序、桶排序、索引排序及冒泡排序优化进行分析。 升序排：从小到大排序，降序排：从大到小排序 冒泡排序 冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序比较次数(n*(n-1))/2 有如下公共代码： import random ls=[] n=5 for i in range(n): ls.append(random.randint(10,100)) for i in range(n-1): for j in range(n-1,i,-1): if ls[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] 降序排(从后往前冒泡） for i in range(n-1): for j in range(n-1,i,-1): if ls[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.1 for i in range(n-1): for j in range(0,n-i-1): if ls[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] 升序排(从前往后冒泡） for i in range(n-1): for j in range(1,n-i): if ls[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] 降序排(从前往后冒泡） for i in range(n-1): flag=False for j in range(n-1,i,-1): if ls[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=True If flag==False： break 冒泡优化1 k = n - 1 last = 0 for i in range(n - 1): flag = True for j in range(k): if ls[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 = j flag = False k = last if flag: break 冒泡优化2 表1.2 选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了。 有如下公共代码： import random ls=[] n=5 for i in range(n): ls.append(random.randint(10,100)) for i in range(n-1): k=i for j in range(i+1,n): if ls[j]<ls[k]: k=j if k!=i: ls[k],ls[i]=ls[i],ls[k] 选择排序写法1 for i in range(n-1