上一节课我们已经讲了算法的基础知识，这节课我们讲一下算法中两个最为经典的类型：排序算法和查找算法。排序和查找我们之前直接使用列表的内置方法，那实现排序和查找最底层的原理是什么呢？我们正式开始这节课的内容吧。
一、排序算法1.1 冒泡排序冒泡排序是最简单的一种排序方法，它的原理是将一列数据中较大（或较小）的数据逐次向右推移的一种排序方法。冒泡排序分为内外两层循环。外层是总共要跑的遍数，2个数据比较一遍，3个数据比较一遍，以此类推，n个数据就跑了n-1遍。内层循环真正比较数据。以升序为例，每次比较把较大的放到后面。由于每一遍都是将本遍最大的数据移动到最右边。就像是水中的气泡一样，小的气泡上升，就排到最上面，就像是“冒泡”一样，所以我们称它为冒泡排序。
下面我们以升序为例，讲一下冒泡排序的基本思想：
第一遍从第1个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较完最后一个元素为止。第一遍排序结束时，最后一个元素是所有元素中的最大值。
第二遍从第一个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较到倒数第二个元素为止。第二遍排序结束时，倒数第二个数为第二大的数。
……
n个数排序共需要n-1遍。
我们看一下模拟的实例：
3 9 2 1 6 原始数据3 9 2 1 6 将3和9比较，不交换位置3 2 9 1 6 将9和2比较，交换位置3 2 1 9 6 将1和9比较，交换位置3 2 1 6 9 将9和6比较，交换位置。第一轮结束2 3 1 4 9 将3和2比较，交换位置2 1 3 4 9 将3和1比较，交换位置2 1 3 4 9 将3和4比较，不交换位置。第二轮结束……
下面我们看一下冒泡排序的Python代码实现：
a = [3, 9, 2, 1, 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个元素到第n个元素中找出一个最小的元素，如果它不是第1个元素，就让它和第1个元素交换位置。第一遍排序结束时，第1个元素为所有元素中的最小值。
第二遍从第2个元素到第n个元素中找出一个最小的元素，如果它不是第2个元素，就让它和第2个元素交换位置。第二遍排序结束时，第2个元素为所有元素中第二小的值。
……
下面我们看看如何实现最小元素的交换位置：
第i遍排序开始时，先假设第i个位置上的数是最小的数，用k标记。让k位置上的数(a[k])与i后面的数(a[j])逐个比较，当找到一个比k位置上小的数，用k记录j的值。当j到达最后一个数时，一遍比较结束，k指向最小的数，即k记录最小的数的位置。当i≠k时，交换a[i]与a[k]的值。
我们看一下选择排序的Python代码实现：
a = [3, 9, 2, 1, 6]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)
插入排序是先将待排序的数列中的第1个元素看成一个有序的子数列，然后从第2个元素开始，将数据逐个插入这个有序的子数列中，以此类推到最后一个数据。整个排序的过程类似于玩扑克牌时一边抓牌一遍理牌的过程，每抓一张牌就把它插入到应有的位置上。
插入排序的整个过程如下图所示：
插入排序
第1次插入，将第2个元素与第1个元素比较。先将要插入到数a[1]放入一个空的变量key；将key与前面已经排好序的元素比较，如果key<a[0]成立，说明key要插入到a[0]前面，将a[0]向后移动一个位置，放到a[1]中，再将key放到a[0]中；如果key<a[0]不成立，说明key要插入到a[0]后面，放key放入到a[1]的位置中。
第2次插入，前面两个元素已经排好序，将第3个元素放入一个空的变量key，将key与前面排好序的元素比较，再将它插入对应的位置中。
……
依次类推。
我们看一下插入排序的Python代码实现：
a = [3, 9, 2, 1, 6]count = len(a)for i in range(1, count): key = a[i] j = i - 1 while j >= 0 and a[j] > key: a[j 1] = a[j] j -= 1 a[j 1] = keyprint(a)
以上三种排序的算法外，还有归并排序、快速排序、堆排序、计数排序、桶排序、希尔排序等等，快速排序的思想下节课我们会讲解，归并排序这里就略去不讲了，大家可以自己研究。别的排序算法相对较为复杂，目前阶段不需要大家掌握。有兴趣的同学可查阅相关资料。
相对好理解一些的是归并排序（暂时不需要掌握代码），大家可以看动画的图片做相应的理解：
归并排序
二、查找算法2.1 顺序查找顺序查找是一种最为常用的查找算法。我们生活中也经常会用到，比如我们要从一堆书里面找到我们想要的书，我们会从第一本开始一本一本地看，直到找到我们想要的那本书。
顺序查找的基本思想是从第一个元素开始，按顺序逐个将数据与给定的数据进行比较，如果某个数据与给定的数据相等，则查找成功，输出所查数据；反之则未找到。
顺序查找的代码使用Python实现也非常简单：
data = [12, 23, 1, 89, 34, 13, 78, 67, 54]key = 34 # 要查找的元素x = -1 # 要查找元素的索引count = len(data)for i in range(0, count): if data[i] == key: x = i breakif x == -1: # -1代表元素未找到 print('元素不存在')else: print(x)
对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是被查找的序列是有序的。
我们思考一个问题，从1到100中随机一个数字，猜出这个数是多少。如果我们从1开始一个个往后猜，每次只能排除一个数字，最坏的情况我们可能要猜100次。但是如果第一次猜50，告诉你大了或者小了。下次再猜25，再下次猜12，以此类推，不管是哪个数字，最多7次之内就能猜出来了。这样比起顺序查找要省了很多的时间。这就是对分查找算法。
我们看看对分查找的思路：
如果key是我们需要查找的值，列表a中存放了n个已经升序排列的元素，m为查找范围[i, j]的中间位置。我们查找的过程中必然是以下三种情况之一：
- 如果key < a[m]，key在前半部分，新的查找范围在[i, m-1]中
- 如果key = a[m]，找到需要对数据
- 如果key > a[m]，key在后半部分，新的查找范围在[m 1, j]中
我们看一下对分查找的Python代码实现：
data = [2, 34, 36, 47, 51, 53, 59, 62, 75, 79, 82]key = 47 # 需要查找的元素count = len(data)i, j = 0, count - 1x = -1while i <= j: m = (i j) // 2 if key == data[m]: x = m break elif key > data[m]: i = m 1 else: j = m - 1if x == -1: print('未找到元素')else: print(x)
1、选择题
列表l = [9, 2, 8, 6, 3, 4]，采用选择排序进行升序排序，第二遍排序之后的结果是（）
A. [2, 3, 8, 6, 9, 4]
B. [2, 8, 6, 3, 4, 9]
C. [2, 6, 3, 4, 8, 9]
D. [2, 3, 4, 6, 8, 9]
2、选择题
列表l = [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]
3、选择题
某个列表中有7个元素，依次为19、28、30、35、39、42、48。如果采用对分查找法在列表中查找元素48，需要查找的次数是（）
A. 1 B. 2 C. 3 D. 4
四、上节课思考题答案1、C
2、C
3、参考代码
n = 0 # 统计个数for i in range(100, 1000): a = i // 100 # 百位数 b = i % 100 // 10 # 十位数 c = i % 10 # 个位数 if a ** 3 b ** 3 c ** 3 == i: n = 1 print(i)print("合计个数：", n)