(
课件网) 四、 冒泡排序算法及程序实现 第五章 数据结构与算法 知识过关 3. 冒泡排序的核心代码(以升序排序为例,对列表a进行排序,也可以使用函数形式) (1)从后往前,小数往前冒。 n=len(a) for i in range(1,n): for j in range(n－1,i－1,－1): if a[j－1]>a[j]: a[j],a[j－1]=a[j－1],a[j] (2)从前往后,大数向后沉(变形)。 n=len(a) for i in range(1,n): for j in range(0,n－i): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] 4. 冒泡排序的优化 冒泡排序中,若在某一遍排序的过程中未发生数据交换,则意味着数据已经有序,可以直接结束该冒泡排序。利用该特性,可以优化冒泡排序的程序代码(参考例4)。 典例精选 【例1】 (2023·浙江1月选考)列表s中包含了8个互不相等的元素,即s[0],s[1],s[2],…,s[7],有如下Python程序段: n=8 for i in range(1,n－1): for j in range(1,n－i－1): if s[j]>s[j－1]: s[j],s[j－1]=s[j－1],s[j] 该程序段实现的是( ) A. s[0]到s[5]的降序排列 B. s[1]到s[6]的降序排列 C. s[1]到s[7]的升序排列 D. s[2]到s[6]的升序排列 A 【解析】 本题考查冒泡排序算法思想。已知外循环变量i的取值范围是[1,6]。当第一轮比较(i为1)时,内循环变量j的取值范围是[1,5],由于参与比较的两元素下标分别是j和j－1,故列表中仅元素s[0]~s[5]从前向后进行比较。再观察分支语句条件s[j]> s[j － 1]可知,当后一个数大于前一个数时要发生交换,故最终排序结果是降序。A正确。 【例2】 有如下Python程序段: k = 1 for i in range(0,len(a)－1): if k*a[i] >k*a[i+1]: a[i],a[i+1] = a[i+1],a[i] k=－k 若列表a有7个元素,运行该程序后,a可能的值是( ) A. [7,8,5,9,6,9,7] B. [7,6,5,8,7,9,9] C. [8,6,7,5,9,7,9] D. [7,8,6,5,7,9,9] A 【解析】 本题考查冒泡排序知识。程序中,当i的值为偶数时k=1,i的值为奇数时k=－1,k的值依次为1、－1、1、－1……交替变换。由条件“k * a[i]> k * a[i + 1]”可知,当k=1时,程序运行后满足a[i]<=a[i + 1];当k=－1时,程序运行后满足a[i]>=a[i + 1]。程序运行后,对于列表a中的数据,满足索引值为偶数的数值必定小于等于其下一个相邻数值,索引值为奇数的数值必定大于等于其下一个相邻数值。A正确。 【例3】 随机生成n个范围是[10,59]的不重复随机整数,并用冒泡排序将其升序排列后输出。Python代码如下,运行界面如图所示。 import random a=[0]*10 b=[False]*100 i=0 while i<=9: x=random.randint(10,59) while _____: x=random.randint(10,59) a[i]=x b[x]=True i=i+1 print(a) def bub_sort(d): n=len(d) for i in range : #① for j in range : #② if d[j]>d[j+1]: d[j],d[j+1]=d[j+1],d[j] bub_sort(a) print(a) [10,16,15,50,30,26,13,23,47,54] [10,13,15,16,23,26,30,47,50,54] b[x]==True (1,n) (0,n－i) 请回答下列问题: (1)请在画线处填入合适的代码。 (2)加框处①的代码能否修改为(0,n－1)或(n－1,0,－1) _____ (3)加框处②的代码能否修改为(n－i－1,－1,－1) _____ 【解析】 (1)此处考查不重复随机数知识。列表b用于标记列表a中的数是否已经存在,False表示没有,True表示已经存在,因此若b[x]的值为True,则表示列表a中已经存在x,该值必须重新生成。(2)冒泡排序的外循环用于控制冒泡 ... ...
