资源简介

专题17　排序算法
学业要求 知　识　点 学业水平等级
1.从相邻数据比较和交换的本质理解冒泡排序的算法思想 4
2.通过对内、外循环和比较语句的功能，用程序代码实现冒泡排序 4
知识点一　冒泡排序算法思想
【知识梳理】
1.________(sorting)是使系列中的元素按照某个字段的值递增(或递减)的次序重新排列的操作。在排序的过程中，元素的值保持不变，但其在系列中的顺序可能会改变。
2.待排序的数据存储方式一般有________和链表两种方式，利用数组存储数据，在排序时需要对数据本身进行物理重排，可能需要移动数据的位置，而利用链表存储数据，只需要修改指针即可。
3.常见的排序算法有________排序、选择排序、插入排序、快速排序、堆排序、归并排序、桶排序等。在选择排序的算法时，可以根据待排序数据自身的特点来选择相应的算法。
4.冒泡排序(Bubble__Sort)是在一系列数据中对________两个数依次进行比较和调整，让较大的数“下沉(上冒)”，较小的数“上冒(下沉)”的一种排序技术。
5.冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数据进行比较，将较________的数据换到上面的一个元素中(升序)。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小的数据已经“上浮”到第一个元素的位置(升序)。然后对余下的n－1个元素重复上述处理过程，直达最后进行余下两个数据的比较和交换。
6.对于n个元素的数组，共需要________遍加工，第一遍加工的比较次数为________次，第二遍加工的比较次数为n－2次，以此类推，最后一遍加工的比较只需________次。所以用冒泡排序算法进行排序时，共需比较n(n－1)/2(次)。其时间复杂度为________。
【经典案例】
冒泡排序特征是对相邻两个数依次进行比较和交换，外循环决定了排序的趟数和有序数据的位置，内循环决定了排序的方向和排序区间，比较语句决定升降序方式。排序往往先找出一列数中的最值，将这个最值交换到该列数的末端，把数列划分为有序区间和无序区间，把这个操作称为一趟排序。再对无序区间进行重复操作，不断地扩大有序区间，缩小无序区间，当无序区间中只有一个数据时，全部数据有序，结束排序。排序基本算法思想是迭代执行一趟排序，直到数据全部有序，因此描述并画出第i趟排序的算法，让学生能看得见排序的过程，是理解排序算法本质思想的关键。
【例1】 采用冒泡排序算法对某数据进行降序排列，经过第一轮排序后的结果是“2，3，4，1，5，0”，那么原数据序列不可能的是(　　)
A.2，3，0，4，5，1 B.0，2，3，4，1，5
C.1，2，3，4，0，5 D.2，0，3，4，1，5
思维点拨
明考向 本题考查冒泡排序的算法思想。从第一轮排序后的结果来看，0是最小值，最值出现的位置在后面，因此属于从前往后的降序排列
精点拨 A 一轮后应为2，3，4，5，1，0，与题目要求不符
B 从前往后将0推到最后
C 1依次和2，3，4交换，0和5交换
D 0依次为3，4，1，5交换
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 采用冒泡排序算法对某数据序列进行排序，第一轮排序后的结果是“2，8，6，3，5，7，9”，则第二轮排序需要交换的次数为(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
【例2】 某Python程序如下：
s＝[2，3，4，9，7，8，5]
n＝len(s)
for i in range(n－1)：
for j in range(n－1，i，－1)：
if s[j]　　　 　s[j]，s[j－1]＝s[j－1]，s[j]
下列说法正确的是(　　)
A.整个加工过程总的交换次数为21
B.该程序段执行后，s的值为[9，8，7，5，4，3，2]
C.若s的初始值已有序，则该算法的时间复杂度为O(1)
D.每一遍加工中，最小的元素“上浮”
思维点拨
明考向 本题考查排序算法
精点拨 A 当条件s[j]B 应为升序排列，而不是降序排列
C 若s已经有序，程序没有作优化，还是要比较，但不交换，因此时间复杂度为O2
D 排序过程中小的数据往前移动，形象地看成是上浮
听课笔记：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 列表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]的升序排列
知识点二　冒泡排序的应用
【知识梳理】
1.排序比较对象若为a[j]和a[j＋2]，则实现奇偶位________排序。
2.当排序的条件有两个或多个时，或者出现了多分支的选择结构，实现的________排序。
3.若每趟交换的次数为0，表示所有数据均________序，可以提前结束排序算法。也可以记flag的状态为False，若发生交换，将flag的值修改为True，根据flag的值，也可以表示数据是否有序。
4.从后往前冒泡的每趟排序实现了[0，i]之间的数据有序，因此下趟排序的区间为[________，n－1]。记录第i趟排序最后一次交换(a[j]和a[j－1]比较)后的有序位置j－1，此时表示[0，j－1]已经有序，下趟排序的区间可以修改为[j，n]，缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
5.从前往后冒泡的每趟排序实现了[n－i，n－1]之间的数据有序，因此下趟排序的区间为[0，________]。记录第i趟排序最后一次交换(a[j]和a[j＋1]比较)后的有序位置j＋1，此时表示[j＋1，n]已经有序，下趟排序的区间可以修改为[0，j]，缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
【经典案例】
在排序过程中，若不要求全部数据有序，而是挑出前n个数据，可以设置条件，提前结束排序。若排序的对象分组依次存储，可以在内循环中设置步长，起到分组排序的目的。还可以在比较语句中设置多个比较条件，实现多关键字的排序。甚至用while循环来表达外循环，根据每趟排序的有序区间，设置外循环i的终值，缩小下趟排序的区间，减少排序的次数。
【例1】 有如下Python程序段：
m＝3
lst＝[7，3，4，3，1，6，3]
for i in range(len(lst)－1)：
　 for j in range(len(lst)－1，i，－1)：
　 if lst[j]　　 　 lst[j]，lst[j－1]＝lst[j－1]，lst[j]
break
执行该程序段，加框处语句被执行的次数是(　　)
A.3 B.4
C.5 D.6
思维点拨
明考向 本题考查冒泡排序的算法思想
精点拨 提前结束排序的条件必须满足两个，其一大于等于m，其二是最后的数据与前面的数据不能相等。如要排出前3名，且有很多并列第3名(排好序[1，3，3，3，4，6，7]，需要找到4即最后一个不符合条件的数据，才能终止循环
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 数组a包含10个不同的元素，即a[0]，a[1]，…a[9]，有如下Python程序段：
n＝len(a)
for i in range(0，n，2)：
for j in range(n－2，i＋1，－2)：
if a[j]　　　　 a[j]，a[j－2]＝a[j－2]，a[j]
该程序段实现的功能是(　　)
A.仅对奇位元素a[0]，a[2]，…a[8]升序排列
B.仅对偶位元素a[1]，a[3]，…a[9]升序排列
C.奇位元素 a[0]，a[2]，…a[8]升序，偶位元素降序排列
D.奇位元素 a[0]，a[2]，…a[8]降序，偶位元素升序排列
【例2】 有实现冒泡排序的Python程序段：
a＝[4，6，3，9，1，2]
n＝len(a)
i＝n－1
while i>＝1：
k＝0
for j in range(i)：
if a[j]　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　k＝j
____________
则划线处的语句应为(　　)
A.i＝k－1 B.i＝k
C.i＝k＋1 D.i＝j
思维点拨
明考向 本题考查冒泡排序的算法思想
精点拨 从内循环来看，实现从前往后冒泡排序，后面的数据先有序，用变量k记录最右边有序的数据位置j＋1，则有序区间为[j＋1，n－1]，待排序区间为[0，j]，用变量k指向j，下趟排序只要j＋1指向k就可以终止本趟排序。第1趟结果为[6，4，9，3，2，1]，下趟排序终点为4；第2趟结果为[6，9，4，3，2，1]，下趟排序终点为1；第3趟结果为[9，6，4，3，2，1]，下趟排序终点为0
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 列表s中包含n个互不相等的元素，用Python编程实现如下功能：s[0]到s[n－1]降序排序，当序列已经有序时结束排序，部分代码如下：
n＝len(s)
for i in range(1，n)：
for j in range()：
if：
　 　　s[j]，s[j－1]＝s[j－1]，s[j]
　　　flag＝True
if flag＝＝False：
break
上述程序段中方框可选代码为：①flag＝True　②flag＝False　③1，n－i＋1　④1，n－i　⑤s[j]s[j－1]，则(1)(2)(3)处代码依次为(　　)
A.②④⑥ B.②③⑥
C.①④⑤ D.①③⑥
1.对一组数据采用冒泡排序算法进行排序，若第一趟排序完成后的数据序列为：31，24，23，15，20，10，则该数据序列的原始顺序不可能的是(　　)
A.24，23，15，31，10，20
B.24，23，15，20，31，10
C.24，31，23，15，10，20
D.23，24，15，20，31，10
2.采用冒泡排序对数据序列“15 89 60 34 10 28 70”完成升序排序，在排序过程中，数据“60”发生交换的次数分别可能为(　　)
A.2 B.3
C.4 D.5
3.采用冒泡排序算法，对某数组数据进行排序，经过一轮后的结果是“2，3，9，5，6，7”，那么下列说法不正确的是(　　)
A.这轮排序，有可能没发生数据交换
B.这轮排序，有可能只发生了1次数据交换
C.排序结束后，数据是升序的
D.完成全部排序后，数据交换的次数和冒泡的方向无关
4.采用冒泡排序算法对数据序列“8，3，5，2，0，9”进行排序，第一轮排序后的结果为“0，8，3，5，2，9”，则整个序列完成排序的交换次数是(　　)
A.6次 B.7次
C.8次 D.9次
5.采用冒泡排序算法对数据序列“7，3，8，2，1，9”进行排序，第一轮排序后的结果为“3，7，2，1，8，9”，则完成整个排序需要交换的次数是(　　)
A.6次 B.7次
C.8次 D.9次
6.如下Python程序段：
s＝list(″bcaabca″)
n＝len(s)
for i in range(1，n)：
　 for j in range(n－1，i－1，－1)：
　if s[j]＝＝'a' and s[j－1]！＝'a'：
　　 　s[j]，s[j－1]＝s[j－1]，s[j]
print(s)
执行该程序段后，输出的内容为(　　)
A.['b'，'c'，'b'，'c'，'a'，'a'，'a']
B.['b'，'b'，'c'，'c'，'a'，'a'，'a']
C.['a'，'a'，'a'，'b'，'c'，'b'，'c']
D.['a'，'a'，'a'，'b'，'b'，'c'，'c']
7.使用列表a和列表b分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i]，使用Python编程实现如下功能：将成绩数据“按总分降序排序、总分相同按学号升序排序”，代码如下。
n＝len(a)
for i in range(1，n)：
for j in range(0，n－i)：
　 if or and ：
　 　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
　 　　　b[j]，b[j＋1]＝b[j＋1]，b[j]
上述程序段中方框处可选代码为：①a[j]>a[j＋1]
②a[j]＝＝a[j＋1]　③a[j]b[j＋1]则(1)(2)(3)处代码依次为(　　)
A.③②④ B.①⑤⑥
C.③②⑥ D.①⑤④
8.列表s包含8个互不相等的元素，即s[0]，s[1]，s[2]，…s[7]，有如下Python程序段：
n＝8
for i in range(1，5)：
for j in range(n－2，i，－1)：
　 if s[j]　　 　s[j]，s[j＋1]＝s[j＋1]，s[j]
该程序段实现的是(　　)
A.s[0]到s[3]的升序排列 B.s[4]到s[7]的升序排列
C.s[2]到s[5]的降序排列 D.s[1]到s[4]的降序排列
专题17　排序算法
知识点一
知识梳理
1.排序　2.数组　3.冒泡　4.相邻　5.小 6.n－1　n－1　1　O(n2)
经典案例
例1　A
变式1　A　[本题考查冒泡排序算法的相关知识。由第一轮数据“2，8，6，3，5，7，9”可知，采用冒泡排序对数据进行升序排序，但有两种可能，一种是从后往前的冒泡升序，则第二轮排序后的数据为“2，3，8，6，5，7，9”，交换2次，另一种是从前往后的冒泡升序，则第二轮排序后的数据为“2，6，3，5，7，8，9”，交换4次。]
例2　D
变式2　A　[本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1，5]，条件s[j]>s[j－1]表示当后一个数大于前一个数时要发生交换，实现降序排列。参加排序元素仅s[0]～s[5]。]
知识点二
知识梳理
1.分组　2.多关键字　3.有　4.i＋1　5.n－i－1
经典案例
例1　C
变式1　A　[本题考查冒泡排序的算法思想。内循环j，初值为n－2＝8，步长为－2，因此j的值为8至2的偶数。比较对象也是这些位置中的数，因此仅实现这些数的升序排列。]
例2　D
变式2　B　[本题考查冒泡排序算法的程序实现，着重考查冒泡排序的优化。(1)逻辑变量flag表示该遍排序中是否有进行数据交换，没有交换提前结束排序。(2)确定每次排序时比较的范围，因外循环变量i的范围为[1，n)，当i＝1时，比较的范围应为[1，n)，当i＝2时，比较的范围应为[1，n－1)，依次类推，随着i值的增加，排序范围的终值在缩小，故填空(2)处应填入“1，n－i＋1”。(3)处确定排序方式是“升序”或“降序”，由于比较的元素为s[j]与s[j－1]，若要实现降序排序，应将较大值换到前面，故填空(3)处应填入“s[j]>s[j－1]”。]
当堂过关检测
1.D　[A、B选项符合从后往前比较，将最小数交换到最前面，C选项符合从前往后比较，将最大的数交换到最右边。而D选项不管从哪个方向进行依次比较，都不符合。]
2.C　[本题主要考查选择排序和冒泡排序的算法思想。冒泡排序中第一趟排序结果为10，15，89，60，34，28，70，60被交换1次，第二趟排序结果为10，15，28，89，60，34，70，60被交换1次，第三趟排序结果为10，15，28，34，89，60，70，60被交换1次，第四趟排序结果为10，15，28，34，60，89，70，60被交换1次，此后的交换与60无关，60共被交换4次。]
3.A　[本题考查冒泡排序。经过一轮后最小数在最前面，可知，该冒泡排序是从后往前冒泡，升序。A选项原始数据最小数2不在最前面，一定会发生交换。若原始数据就是一趟排序结果，9在中间，无论是从后往前，还是从前往后，都要发生数据交换。B选项若原始数据如果为“2，3，5，9，6，7”，那么就发生了一次交换。C选项从一趟结果来看，是升序排列。D选项数据的交换取决于逆序对的个数，与排序方向无关。]
4.D　[本题考查冒泡排序算法思想。数据序列最大值和最小值分别为9和0，若实现从后往前升序排列，符合题目描述。若实现从前往后升序，结果应为“3，5，2，0，8，9”。无论排序的方向如何，只要是实现升序，8换到相应位置需交换4次，3和5换到相应位置各需交换2次，2换到相应位置，需交换1次。]
5.C　[本题考查冒泡排序的算法思想。从第一轮排序后的结果来看，实现从前往后升序排列，只要找出序列中的逆序对，就可以判断交换次数。7和后面的3，2，1是逆序对，3和2，1是逆序对，8和2，1是逆序对，2和1是逆序对，共有8组逆序对。]
6.C　[本题考查冒泡排序的变形。根据if条件s[j]＝＝'a' and s[j－1]！＝'a'可以看出，取字符串s中字符时，若当前字符s[j]为'a'但s[j－1]不为'a'，交换s[j－1]与s[j]的位置。因此，该程序段的功能为将字符'a'前移，其他字符保持原位置不变，交换后的结果为C选项['a'，'a'，'a'，'b'，'c'，'b'，'c']。]
7.C　[本题考查冒泡排序。从for j in range(0，n－i)可知，从前向后冒泡，相邻两数两两比较；比较规则如下：第j个比j＋1个成绩小则交换③，第j个和第j＋1个成绩相同②且第j个考号比第j＋1个大⑥。]
8.C　[本题考查冒泡排序算法思想。从后往前冒泡，前面的数据先有序，有序区间的左端点是i＋1，比较对象是s[j]

展开更多......

收起↑