掌握冒泡排序、选择排序、插入排序、顺序查找、对分查找的的基本原理，并能使用这些算法编写简单的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 = ifor 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 = ifor j in range(i+1, count):if a[k] > a[j]:k = jif 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 -= 1if 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 = ibreak
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    # 将目标元素的索引赋值给bbreak    # 找到目标元素，停止查找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 randommaxn = 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 - 1while _____2_____ :i -= 1if i == key:key += 1else:a.remove( ____3____ )n -= 1for 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 - 1while 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 += 1else:ret.append(b[j])j += 1if 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:]