第15课 算法（下）
掌握冒泡排序、选择排序、插入排序、顺序查找、对分查找的的基本原理，并能使用这些算法编写简单的Python程序。
一、冒泡排序
1、冒泡排序的概念
冒泡排序是最简单的排序算法，是在一列数据中把较大（或较小）的数据逐次向右推移的一种排序技术。
冒泡排序过程容易理解，每一轮加工都是将本轮最大（或最小）的数据移动至右端。每个数如同水中的气泡一样，小的气泡上升，被排到最上面；大的气泡依次排在下面，这样的过程可以比喻成“冒泡”。
2、冒泡排序的基本思想（以升序为例）
依次比较相邻的两个数，将小数放在前面，大数放在后面。
第一轮从第1个元素开始，让它和第2个元素进行比较，若出现反序（大数在前，小数在后）则交换；然后让第2个元素与第3个元素进行比较，若出现反序则交换；依次类推，直到比较完最后一对元素为止。第一轮排序结束时，最后一个元素为所有元素中的最大值。
接下来进行第二轮比较。还是从第1个元素开始，让它和第2个元素比较，若出现反序则交换；然后让第2个元素和第3个元素进行比较，若出现反序则交换；依次类推，直到比较完最后一对元素（即倒数第二对数）为止。这样，倒数第二个数为第二大的数。
依次排序下去，n个数排序共需要进行n-1轮。
示例模拟：
5 8 4 3 7
5 8 4 3 7 将5和8比较，不交换位置
5 4 8 3 7 将8和4比较，交换位置
5 4 3 8 7 将8和3比较，交换位置
5 4 3 7 8 将8和7比较，交换位置，8被移至末尾
3、冒泡排序算法框架（伪代码）
冒泡排序采用双层嵌套循环来实现，外侧循环控制排序的轮数，内层循环控制排序元素下标的变化、以及数据对的比较。
for i (0 ~ n-1) # 共进行n-1轮排序
for j (0 ~ n-1-i) # 第i轮排序（次数）
if 数据对反序，则:
数据交换
4、冒泡排序程序的实现（升序）
a = [1, 3, 2, 5, 8, 7, 6]
count = len(a)
for i in range(0, count-1):
for j in range(0, count-1-i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print(a)
运行结果如下：
[1, 2, 3, 5, 6, 7, 8]
思考一下，若要将列表中的元素降序排列，应该如何修改程序？
是不是只需要将上述代码中的大于号改成小于号即可？
5、思考题
（1）某书店在5所学校的流动售书量（单位为本）分别是80、125、64、68、46。采用冒泡排序对其进行升序排列，完成第二轮时的结果是（ ）
（2）有一组原始数据：23、25、18、63、84、77、65、9、33、17。使用冒泡排序算法进行从小到大排序，最多需要进行（ ）轮加工，才可以完成整个数据的排序。
A、5 B、6 C、8 D、9
二、选择排序
1、选择排序的概念
选择排序算法是对冒泡排序算法的改进。
选择排序是在参加排序的所有元素中找出数值最小（或最大）的元素，如果它不是在左侧第一个元素，就让它和最左侧第一个元素互换位置；然后在余下的元素中找出数值最小（或最大）的元素，如果它不在左侧第二个元素，就让它和最测第二个元素叫唤位置；以此类推，直到所有元素成为一个有序的序列。
选择排序算法符合人们日常的排序习惯。
在对n个元素排序的时候，选择排序算法和冒泡排序算法的比较次数是相同的，但交换次数比冒泡排序要少，因此它具有更高的效率。
2、选择排序的基本思想
n个数排序共需要进行n-1轮。以从小到大排序为例：
第一轮，从第1个元素到第n个元素中找出一个最小的元素，如果它不是第1个元素，就让它和第1个元素交换位置。第一轮排序结束时，第1个元素就是最小的元素。
第二轮，从第2个元素到第n个元素中找出一个最小元素，如果它不是第2个元素，就让它和第2个元素交换位置。第二轮排序结束时，第2个元素就是第2小的元素。
以此类推，第i轮排序，中第i个元素到第n个元素中找出一个最小的元素，最小元素的索引记作k，如果最小元素不在第i位上，即k!=i，就把最小元素和第i个元素叫唤位置，即：序列[i], 序列[k] = 序列[k], 序列[i]。
直到只剩下最后一个元素，排序结束。最后一个元素就是最大的元素。
3、选择排序算法框架（伪代码）
选择排序算法同样采用双层嵌套循环来实现，外侧循环用来控制排序的轮数，内层循环用来控制排序元素的下标变化范围。每一轮排序过程中，都需要一个临时变量存储本轮排序中最小元素（或最大元素）的下标。
for i in (0 ~ n-1) # 共进行n-1轮排序
k = i
for j in (i+1, n) # 第i轮排序（次数）
if 找到一个比k位置更小的元素，则：
用k记录j的位置
if i != k， 则：
交换i和k位置上的数据
4、选择排序程序的实现（升序）
a = [3, 4, 1, 2, 0, 9, 10]
count = len(a)
for i in range(0, count-1):
k = i
for j in range(i+1, count):
if a[k] > a[j]:
k = j
if k != i:
a[k], a[i] = a[i], a[k]
print(a)
运行结果如下：
[0, 1, 2, 3, 4, 9, 10]
思考一下，如果按照降序排列，该如何修改程序？
体会变量k的用意。
与冒泡排序相比，选择排序的优劣是什么？
5、思考题
（1）用选择排序算法对一组学生的身高数据进行升序排序，已知第一轮排序结束后的数据序列为：166、169、177、175、172，则下列选项中可能是原始数据序列的是（ ）。
A、175、177、169、166、172
B、177、169、166、175、172
C、166、177、169、175、172
D、166、169、172、175、177
（2）某校要采购一套多媒体教学设备，有5个参考价位，分别如下：18万元、17万元、23万元、15万元、16万元。若采用选择排序算法对价格从高到低排序，需要进行数据交换的次数是（ ）。
A、1 B、3 C、4 D、5
（3）下列关于排序的说法，错误的是（ ）。
A、相对而言，选择排序算法的效率比冒泡排序算法的效率高
B、冒泡排序算法和选择排序算法都需要用到双循环结构
C、对于n个无序数据，不管是冒泡排序还是选择排序，都需要经过n-1轮加工
D、冒泡排序算法的程序实现一般要用到数组变量k，而选择排序则不需要
三、插入排序
1、插入排序的概念
插入排序算法过程如下：先将待排序数列中的第1个元素看成一个有序的子序列，然后从第2个元素起，将其依次（从小到大或从大到小）逐个插入这个有序的子序列中，以此类推到最后一个元素。这很像完扑克牌时一边抓牌一边理牌的过程，每抓到一张牌，就把它插到应处的位置。
2、插入排序的基本思想
先将列表中的前两个元素按顺序排列（以升序为例）。
然后，每次将下一个待排序元素，按其大小插入到前面已经排好顺序的序列中，使序列依旧有序，直到所有待排序元素全部插入完成。
3、实例演示
已知列表a=[5, 3, 5, 2, 8]，对其升序排列。
第一轮插入（只要将第2个元素与第1个元素比较）
（1）先将待插入的元素a[1]暂存到变量key中；
（2）将key与前面已经排序好的元素比较，key<a[0]成立，说明key要插入到a[0]前面，将a[0]往后移一个位置，放到a[1]中；
（3）将key放入a[0]中。
第二轮插入（将第3个元素插入前面已排好的两个元素序列中）
（1）先将待插入的元素a[2]暂存到变量key中；
（2）将key与前面已经排好序的元素比较，key<a[1]不成立，说明key要插入到a[1]后面，即a[2]中；
（3）将key放入a[2]中。
第三轮插入（将第4个元素插入到前面已排好的三个元素序列中）
（1）先将待插入的元素a[3]暂存到变量key中；
（2）将key与前面已经排序序的序列比较，key<a[2]成立，说明key要插入到a[2]前面，将a[2]后移一位，放到a[3]中；
（3）再比较前一个元素，key<a[1]成立，说明key要插入到a[1]前面，将a[1]后移一位，放到a[2]中；
（4）再比较前一个元素，key<a[0]成立，说明key要插入到a[0]前面，将a[0]后移一位，放到a[0]中；
（5）将key放入a[0]中。
第四轮插入（将第5个元素插入到前面已排好的4个元素序列中）
与第二次插入类似，第个元素比a[3]大，应该插入到a[3]后面，即位置保持不变。至此，插入排序完成。
4、插入排序程序实现
示例程序（1）
a = [5, 3, 5, 2, 8] # 初始化一个列表
for i in range(1, len(a)): # 设定插入的轮数
key = a[i] # 将待排序元素暂存到变量key中
j = i - 1 # 将待比较元素的索引存入变量j中
while j >= 0 and a[j] > key: # 元素比较
a[j+1] = a[j] # 将大元素往后移动
j -= 1 # 更新待比较元素的索引
a[j+1] = key # 将待插入元素往前移动
print(a) # 打印最终结果
运行结果：
[2, 3, 5, 5, 8]
示例程序（2）
a = [5, 3, 5, 2, 8] # 初始化一个列表
for i in range(1, len(a)): # 设定插入的轮数
j = i -1 # 将待比较元素的索引存入变量j中
while j >= 0 and a[j] > a[i]: # 元素比较
j -= 1
if j == 0: # 如果待插入元素最小，将其插入到最前面
a.insert(0, a[i])
else: # 如果待插入元素不最小，将其插入到j+1索引前
a.insert(j+1, a[i])
a.pop(i+1) # 最后将待插入的原始数据删除
print('a =, a') # 打印最终结果
运行结果：
a = [2, 3, 5, 5, 8]
四、顺序查找
查找是程序和现实生活中经常用到的方法，也是一种查询数据的技术，其目标是以较少的步骤或在较短的时间内找到所需的数据。
这里主要掌握顺序查找和对分查找算法。
1、顺序查找的概念
假设要从n个元素中查找元素x是否存在，最原始的方法就是从头到尾依次查找，这种查找方法就是顺序查找。
顺序查找的基本思想是：从第一个元素开始，按顺序逐个将数据与给定的数据（查找键）进行比较，若某个元素与查找键相等，则查找成功，输出所查数据的位置；反之，输出未找到。
2、顺序查找的处理过程
假设列表a中有n个元素，查找键已经存在变量key中。
从列表a中的第1 哥元素a[0]开始，依次判断各元素的值是否与key相等，若某个元素a[i]的值等于key，则找到了指定的数据，对应的位置索引为i，停止程序；若找遍了所有的n个元素，没有一个元素的值等于key，输出未找到，停止程序。
3、顺序查找的程序实现
在列表中查找元素26。
lst = [32, 17, 56, 25, 26, 89, 65, 12] # 初始化列表
key = 26 # 初始化要查找的元素
b = -1 # 要查找元素的索引
m = len(lst) # 列表长度
for i in range(0, m):
if lst[i] == key:
b = i
break
if b == -1: # -1 表示未找到
print("要查找的元素 [" + str(key) + "] 不在列表lst中。")
else:
print("要查找的元素 [" + str(key) + "] 的索引是：" + str(b))
4、思考题
（1）想一想，顺序查找与枚举算法的相似之处与不同之处。
（2）为查找课文第一次描写景色的自然段，小张同学打开课本依次阅读每一个自然段进行查找。这种查找方法为（ ）。
A、无序查找B、顺序查找C、对分查找D、随机查找
（3）在23、41、54、26、84、52、65、21中查找数字52，采用从后往前的顺序查找，需要查找的次数是（ ）。
A、2次B、3次C、7次D、1次
五、对分查找
如果在一堆无序的数列中查找某个数，可以使用顺序查找；如果在一个排好顺序的有序数列中查找某个数，除了顺序查找，你还有更快、更简洁的查找算法吗？
1、对分查找的概念
对分查找又称“二分查找”，是一种高效的查找方法。
对分查找的前提条件：被查找数据序列是有序的（升序或降序排列）。
对分查找的基本思想：首先将要查找的数据与有序数列内处于中间位置上的数据进行比较，如果两者相等，则查找成功；否则根据数据的有序性，再确定该数据的范围应该在数列的前半部分还是后半部分；在新确定的缩小范围内，继续按上述方法进行查找，直到找到要查询的数据，即查询成功；如果要查询的数据不存在，即查找失败。
2、对分查找的处理过程
若key为查找键，列表a存放n个已按升序排序好的元素。在使用对分查找时，把查找范围[i, j]的中间位置上的数据a[m]与key进行比较，结果必然有以下3中情况：
（1）若key<a[m]，查找键key小于中间位置数据a[m]。由于列表a按升序排列，可以确定key的值应该在列表a的前半段，即在新范围（i, m-1）中继续查找。
（2）若key=a[m]，查找成功。
（3）若key>a[m]，查找键key大于中间位置数据a[m]。可以断定key应该在列表a的后半段，所以应该在新范围（m+1, j）中继续查找。
中间位置数据a[m]的下标m的计算方法如下：
m = (i+j)//2 或 m = int((i+j)/2)
3、对分查找的程序实现
（1）由于比较次数难以确定，所以用while语句实现循环。
（2）在while循环体中用if语句判断查找是否成功。
（3）若查找成功则输出查找结果，并用break语句结束循环。
（4）若查找不成功，则判断查找键在数组的前半段还是后半段，从而缩小范围，继续查找。
假设列表 lst = [12, 17, 23, 25, 26, 35, 47, 68, 76, 88, 96]，要查找元素 key = 25， 使用对分查找程序如下：
# 初始化变量
lst = [12, 17, 23, 25, 26, 35, 47, 68, 76, 88, 96]
key = 25
n = len(lst)
# i为左边的索引号，j为右边的索引号
i, j = 0, n - 1
b = -1
# 执行查找操作
while i <= j: # 只要i小于等于j，就继续查找
m = (i + j) // 2 # 计算中间索引
if key == lst[m]: # 恰好找到目标元素
b = m # 将目标元素的索引赋值给b
break # 找到目标元素，停止查找
elif key > lst[m]: # 如果目标元素在列表后半段
i = m +1 # 将左边的索引移到中间偏后一位
else: # 如果目标元素在前半段
j = m -1 # 将右边的索引移到中间偏前一位
# 查找完成之后，根据索引b的值判断是否查找成功
if b == -1: # -1 表示元素未找到
print("要查找的元素 [" + str(key) + "] 不在列表lst中。")
else:
print("要查找的元素 [" + str(key) + "] 的索引是：" + str(b))
4、对分查找的查找次数估算
对元素规模为n的列表进行对分查找时，无论是否找到，至多进行log2(n)次查找就能得到结果；而使用顺序查找算法，在最坏的情况下需要进行n次查找，在最好的情况下需要查找1次，平均查找次数为(n+1)/2。
5、思考题
（1）下列有关查找的说法，正确的是（ ）。
A、顺序查找时，被查找的数据必须有序
B、对分查找时，被查找的数据不一定有序
C、顺序查找总能找到要查找的关键字
D、一般情况下，对分查找的效率较高
（2）某列表有7个元素，依次为：19、28、30、35、39、42、48。若采用对分查找算法在该列表中查找元素48，需要查找的次数是（ ）。
A、1 B、2 C、3 D、4
六、模拟考题
(一）单选题：
1、编程大赛的成绩排名，可以采用的算法是（ ）。
A、解析算法B、枚举算法C、排序算法D、查找算法
2、对一组初始记录无序的数据：7、9、3、2、5，使用用选择排序算法，按照从小到大顺序排列，则第一轮排序的结果为（ ）。
A、7、 9、 2、 3、 5
B、2、 9、 3、 7、 5
C、2、 7、 9、 3、 5
D、2、 3、 5、 7、 9
3、L=[9, 2, 8, 6, 3, 4]，采用选择排序进行升序排序，第二轮排序后的结果是（ ）。
A、[2, 3, 8, 6, 9, 4]
B、[2, 8, 3, 6, 4, 9]
C、[2, 6, 3, 4, 8, 9]
D、[2, 3, 4, 6, 8, 9]
4、设一组初始记录关键字序列为[5, 2, 6, 3, 7]，利用插入排序算法进行升序排序，则第二次插入排序的结果为（ ）。
A、[5, 2, 3, 6, 7]
B、[2, 5, 3, 6, 7]
C、[2, 5, 6, 3, 7]
D、[2, 3, 5, 6, 7]
5、对于n个元素，利用顺序查找算法，最坏的情况需要查找（ ）次才结束。
A、n B、n / 2 C、n**2 D、log2(n+1)
6、对于n个元素，利用对分查找算法，最坏的情况是查找（ ）次才结束。
A、n B、n / 2 C、n**1 D、log2（n）
(二）编程题
1、在一列表中产生n（n>=10）个50以内的数据，删除其重复的数据并按照升序输出，同时输出删除数据的个数。
例如输入：n = 10
随机产生列表：a = [1, 2, 3, 7, 4, 7, 3, 8, 5, 7]
输出：a = [1, 2, 3, 4, 5, 7, 8]
输出：共删除数据为3个
请编写程序实现上述功能，或补全代码。
import random
maxn = int(input("请输入要产生的数据个数："))
_____1_____
for i in range(maxn):
a.append(random.randrange(1, 50, 1))
print("原始数据：", a)
key, n = 0, maxn
while key < n:
i = n - 1
while _____2_____ :
i -= 1
if i == key:
key += 1
else:
a.remove( ____3____ )
n -= 1
for i in range(n):
for j in range(len(a)-1, i, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = _____4_____
print("去重后排序数据：", a)
print("共删除数据：", ____5____ , "个")
2、对于列表对象a = [7, 4, 7, 3, 9]，用插入排序算法进行升序排序，不分代码如下，请补全代码。
a = [7, 4, 7, 3, 9] # 初始化列表
______1______
for i in range(1, count):
key = ____2____
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
_____3_____
a[j+1] = key
print(a)
3、科技小组分两个小队搜集西红柿生长的数据信息。两个小队都将数据进行了从小大大排序：a = [1, 3, 4, 6, 7, 13, 17, 21]，b = [2, 5, 6, 8, 10, 12, 14, 16, 18]。请将这两个小队的数据进行合并，生成一个从小到大排列的有序列表。
输入：
1,3,4,6,7,13,17,21
2,5,6,8,10,12,14,16,18
输出：
[1, 2, 3, 4, 5, 6, 6, 7, 8, 10, 12, 13, 14, 16, 17, 18, 21]
请编写程序实现上述功能，或补全代码。
x = input()
s = x.split(',')
a = []
for i in range(_____1_____):
a.append(int(s[i]))
y = input()
s = y._____2_____
b = []
for i in range(len(s)):
b.append(int(s[i]))
ret = []
i = j = 0
while len(a) >= i + 1 and _____3_____:
if a[i] <= b[j]:
_____4_____
i += 1
else:
ret.append(b[j])
j += 1
if len(a) > i:
ret += a[i:]
if len(b) > j:
_____5_____
print(ret)
–>参考答案往下翻<–
–>参考答案<–
一、单选题:
1~6：C、B、A、D、A、D
二、编程题：
1、参考答案：
（1）a = []
（2）a[i] != a[key]
（3）a[i]
（4）a[j-1], a[j]
（5）maxn - n
2、参考答案：
（1）count = len(a)
（2）a[i]
（3）j -= 1
3、参考答案：
（1）len(s)
（2）split(‘,’)
（3）len(b) >= j + 1
（4）ret.append(a[i])
（5）ret += b[j:]